001/* 002 * The contents of this file are subject to the terms of the Common Development and 003 * Distribution License (the License). You may not use this file except in compliance with the 004 * License. 005 * 006 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the 007 * specific language governing permission and limitations under the License. 008 * 009 * When distributing Covered Software, include this CDDL Header Notice in each file and include 010 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL 011 * Header, with the fields enclosed by brackets [] replaced by your own identifying 012 * information: "Portions Copyright [year] [name of copyright owner]". 013 * 014 * Copyright 2006-2010 Sun Microsystems, Inc. 015 * Portions Copyright 2011-2017 ForgeRock AS. 016 */ 017package org.opends.server.replication.plugin; 018 019import java.util.Iterator; 020import java.util.Set; 021 022import org.forgerock.opendj.ldap.ByteString; 023import org.forgerock.opendj.ldap.ModificationType; 024import org.forgerock.opendj.ldap.schema.AttributeType; 025import org.opends.server.replication.common.CSN; 026import org.opends.server.types.Attribute; 027import org.opends.server.types.AttributeBuilder; 028import org.opends.server.types.Entry; 029import org.opends.server.types.Modification; 030 031import com.forgerock.opendj.util.SmallSet; 032 033/** 034 * This class is used to store historical information for multiple valued attributes. 035 * One object of this type is created for each attribute that was changed in the entry. 036 * It allows to record the last time a given value was added,the last 037 * time a given value was deleted and the last time the whole attribute was deleted. 038 */ 039public class AttrHistoricalMultiple extends AttrHistorical 040{ 041 /** Last time when the attribute was deleted. */ 042 private CSN deleteTime; 043 /** Last time the attribute was modified. */ 044 private CSN lastUpdateTime; 045 /** Change history for the values of this attribute. */ 046 private final SmallSet<AttrValueHistorical> valuesHist = new SmallSet<>(); 047 048 /** 049 * Create a new object from the provided information. 050 * @param deleteTime the last time this attribute was deleted 051 * @param updateTime the last time this attribute was updated 052 * @param valuesHist the new attribute values when updated. 053 */ 054 AttrHistoricalMultiple(CSN deleteTime, CSN updateTime, Set<AttrValueHistorical> valuesHist) 055 { 056 this.deleteTime = deleteTime; 057 this.lastUpdateTime = updateTime; 058 if (valuesHist != null) 059 { 060 this.valuesHist.addAll(valuesHist); 061 } 062 } 063 064 /** Creates a new object. */ 065 public AttrHistoricalMultiple() 066 { 067 this.deleteTime = null; 068 this.lastUpdateTime = null; 069 } 070 071 /** 072 * Returns the last time when the attribute was updated. 073 * @return the last time when the attribute was updated 074 */ 075 CSN getLastUpdateTime() 076 { 077 return lastUpdateTime; 078 } 079 080 @Override 081 public CSN getDeleteTime() 082 { 083 return deleteTime; 084 } 085 086 /** 087 * Delete all historical information that is older than the provided CSN for 088 * this attribute type. 089 * Add the delete attribute state information 090 * @param csn time when the delete was done 091 */ 092 void delete(CSN csn) 093 { 094 // iterate through the values in the valuesInfo and suppress all the values 095 // that have not been added after the date of this delete. 096 for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();) 097 { 098 AttrValueHistorical info = it.next(); 099 if (csn.isNewerThanOrEqualTo(info.getValueUpdateTime()) && 100 csn.isNewerThanOrEqualTo(info.getValueDeleteTime())) 101 { 102 it.remove(); 103 } 104 } 105 106 if (csn.isNewerThan(deleteTime)) 107 { 108 deleteTime = csn; 109 } 110 111 if (csn.isNewerThan(lastUpdateTime)) 112 { 113 lastUpdateTime = csn; 114 } 115 } 116 117 /** 118 * Update the historical of this attribute after deleting a set of values. 119 * 120 * @param attr 121 * the attribute containing the set of values that were deleted 122 * @param csn 123 * time when the delete was done 124 */ 125 void delete(Attribute attr, CSN csn) 126 { 127 AttributeType attrType = attr.getAttributeDescription().getAttributeType(); 128 for (ByteString val : attr) 129 { 130 delete(val, attrType, csn); 131 } 132 } 133 134 /** 135 * Update the historical of this attribute after a delete value. 136 * 137 * @param val 138 * value that was deleted 139 * @param attrType 140 * @param csn 141 * time when the delete was done 142 */ 143 void delete(ByteString val, AttributeType attrType, CSN csn) 144 { 145 update(csn, new AttrValueHistorical(val, attrType, null, csn)); 146 } 147 148 /** 149 * Update the historical information when values are added. 150 * 151 * @param attr 152 * the attribute containing the set of added values 153 * @param csn 154 * time when the add is done 155 */ 156 private void add(Attribute attr, CSN csn) 157 { 158 AttributeType attrType = attr.getAttributeDescription().getAttributeType(); 159 for (ByteString val : attr) 160 { 161 add(val, attrType, csn); 162 } 163 } 164 165 /** 166 * Update the historical information when a value is added. 167 * 168 * @param addedValue 169 * the added value 170 * @param attrType 171 * the attribute type of the added value 172 * @param csn 173 * time when the value was added 174 */ 175 void add(ByteString addedValue, AttributeType attrType, CSN csn) 176 { 177 update(csn, new AttrValueHistorical(addedValue, attrType, csn, null)); 178 } 179 180 private void update(CSN csn, AttrValueHistorical valInfo) 181 { 182 valuesHist.addOrReplace(valInfo); 183 if (csn.isNewerThan(lastUpdateTime)) 184 { 185 lastUpdateTime = csn; 186 } 187 } 188 189 @Override 190 public Set<AttrValueHistorical> getValuesHistorical() 191 { 192 return valuesHist; 193 } 194 195 @Override 196 public boolean replayOperation(Iterator<Modification> modsIterator, CSN csn, 197 Entry modifiedEntry, Modification m) 198 { 199 if (csn.isNewerThanOrEqualTo(getLastUpdateTime()) 200 && m.getModificationType() == ModificationType.REPLACE) 201 { 202 processLocalOrNonConflictModification(csn, m); 203 return false;// the attribute was not modified more recently 204 } 205 // We are replaying an operation that was already done 206 // on another master server and this operation has a potential 207 // conflict with some more recent operations on this same entry 208 // we need to take the more complex path to solve them 209 return replayPotentialConflictModification(modsIterator, csn, modifiedEntry, m); 210 } 211 212 private boolean replayPotentialConflictModification(Iterator<Modification> modsIterator, CSN csn, 213 Entry modifiedEntry, Modification m) 214 { 215 // the attribute was modified after this change -> conflict 216 switch (m.getModificationType().asEnum()) 217 { 218 case DELETE: 219 if (csn.isOlderThan(getDeleteTime())) 220 { 221 /* this delete is already obsoleted by a more recent delete 222 * skip this mod 223 */ 224 modsIterator.remove(); 225 return true; 226 } 227 228 if (!processDeleteConflict(csn, m, modifiedEntry)) 229 { 230 modsIterator.remove(); 231 return true; 232 } 233 return false; 234 235 case ADD: 236 if (!processAddConflict(csn, m)) 237 { 238 modsIterator.remove(); 239 return true; 240 } 241 return false; 242 243 case REPLACE: 244 if (csn.isOlderThan(getDeleteTime())) 245 { 246 /* this replace is already obsoleted by a more recent delete 247 * skip this mod 248 */ 249 modsIterator.remove(); 250 return true; 251 } 252 253 /* save the values that are added by the replace operation into addedValues 254 * first process the replace as a delete operation 255 * -> this generates a list of values that should be kept 256 * then process the addedValues as if they were coming from an add 257 * -> this generates the list of values that needs to be added 258 * concatenate the 2 generated lists into a replace 259 */ 260 boolean conflict = false; 261 Attribute addedValues = m.getAttribute(); 262 m.setAttribute(new AttributeBuilder(addedValues.getAttributeDescription()).toAttribute()); 263 264 processDeleteConflict(csn, m, modifiedEntry); 265 Attribute keptValues = m.getAttribute(); 266 267 m.setAttribute(addedValues); 268 if (!processAddConflict(csn, m)) 269 { 270 modsIterator.remove(); 271 conflict = true; 272 } 273 274 AttributeBuilder builder = new AttributeBuilder(keptValues); 275 builder.addAll(m.getAttribute()); 276 m.setAttribute(builder.toAttribute()); 277 return conflict; 278 279 case INCREMENT: 280 // TODO : FILL ME 281 return false; 282 283 default: 284 return false; 285 } 286 } 287 288 @Override 289 public void processLocalOrNonConflictModification(CSN csn, Modification mod) 290 { 291 /* 292 * The operation is either a non-conflicting operation or a local operation 293 * so there is no need to check the historical information for conflicts. 294 * If this is a local operation, then this code is run after 295 * the pre-operation phase. 296 * If this is a non-conflicting replicated operation, this code is run 297 * during the handleConflictResolution(). 298 */ 299 300 Attribute modAttr = mod.getAttribute(); 301 AttributeType type = modAttr.getAttributeDescription().getAttributeType(); 302 303 switch (mod.getModificationType().asEnum()) 304 { 305 case DELETE: 306 if (modAttr.isEmpty()) 307 { 308 delete(csn); 309 } 310 else 311 { 312 delete(modAttr, csn); 313 } 314 break; 315 316 case ADD: 317 if (type.isSingleValue()) 318 { 319 delete(csn); 320 } 321 add(modAttr, csn); 322 break; 323 324 case REPLACE: 325 /* TODO : can we replace specific attribute values ????? */ 326 delete(csn); 327 add(modAttr, csn); 328 break; 329 330 case INCREMENT: 331 /* FIXME : we should update CSN */ 332 break; 333 } 334 } 335 336 /** 337 * Process a delete attribute values that is conflicting with a previous modification. 338 * 339 * @param csn The CSN of the currently processed change 340 * @param m the modification that is being processed 341 * @param modifiedEntry the entry that is modified (before current mod) 342 * @return {@code true} if no conflict was detected, {@code false} otherwise. 343 */ 344 private boolean processDeleteConflict(CSN csn, Modification m, Entry modifiedEntry) 345 { 346 /* 347 * We are processing a conflicting DELETE modification 348 * 349 * This code is written on the assumption that conflict are 350 * rare. We therefore don't care much about the performance 351 * However since it is rarely executed this code needs to be 352 * as simple as possible to make sure that all paths are tested. 353 * In this case the most simple seem to change the DELETE 354 * in a REPLACE modification that keeps all values 355 * more recent that the DELETE. 356 * we are therefore going to change m into a REPLACE that will keep 357 * all the values that have been updated after the DELETE time 358 * If a value is present in the entry without any state information 359 * it must be removed so we simply ignore them 360 */ 361 362 Attribute modAttr = m.getAttribute(); 363 if (modAttr.isEmpty()) 364 { 365 // We are processing a DELETE attribute modification 366 m.setModificationType(ModificationType.REPLACE); 367 AttributeBuilder builder = new AttributeBuilder(modAttr.getAttributeDescription()); 368 369 for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();) 370 { 371 AttrValueHistorical valInfo = it.next(); 372 373 if (csn.isOlderThan(valInfo.getValueUpdateTime())) 374 { 375 // this value has been updated after this delete, 376 // therefore this value must be kept 377 builder.add(valInfo.getAttributeValue()); 378 } 379 else if (csn.isNewerThanOrEqualTo(valInfo.getValueDeleteTime())) 380 { 381 /* 382 * this value is going to be deleted, remove it from historical 383 * information unless it is a Deleted attribute value that is 384 * more recent than this DELETE 385 */ 386 it.remove(); 387 } 388 } 389 390 m.setAttribute(builder.toAttribute()); 391 392 if (csn.isNewerThan(getDeleteTime())) 393 { 394 deleteTime = csn; 395 } 396 if (csn.isNewerThan(getLastUpdateTime())) 397 { 398 lastUpdateTime = csn; 399 } 400 } 401 else 402 { 403 // we are processing DELETE of some attribute values 404 AttributeBuilder builder = new AttributeBuilder(modAttr); 405 406 AttributeType attrType = modAttr.getAttributeDescription().getAttributeType(); 407 for (ByteString val : modAttr) 408 { 409 boolean deleteIt = true; // true if the delete must be done 410 boolean addedInCurrentOp = false; 411 412 // update historical information 413 AttrValueHistorical valInfo = new AttrValueHistorical(val, attrType, null, csn); 414 AttrValueHistorical oldValInfo = valuesHist.get(valInfo); 415 if (oldValInfo == null) 416 { 417 valuesHist.add(valInfo); 418 } 419 else 420 { 421 // this value already exist in the historical information 422 if (csn.equals(oldValInfo.getValueUpdateTime())) 423 { 424 // This value was added earlier in the same operation 425 // we need to keep the delete. 426 addedInCurrentOp = true; 427 } 428 if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime()) && 429 csn.isNewerThanOrEqualTo(oldValInfo.getValueUpdateTime())) 430 { 431 valuesHist.addOrReplace(valInfo); 432 } 433 else if (oldValInfo.isUpdate()) 434 { 435 deleteIt = false; 436 } 437 } 438 439 /* if the attribute value is not to be deleted 440 * or if attribute value is not present suppress it from the 441 * MOD to make sure the delete is going to succeed 442 */ 443 if (!deleteIt 444 || (!modifiedEntry.hasValue(modAttr.getAttributeDescription(), val) && ! addedInCurrentOp)) 445 { 446 // this value was already deleted before and therefore 447 // this should not be replayed. 448 builder.remove(val); 449 if (builder.isEmpty()) 450 { 451 // This was the last values in the set of values to be deleted. 452 // this MOD must therefore be skipped. 453 return false; 454 } 455 } 456 } 457 458 m.setAttribute(builder.toAttribute()); 459 460 if (csn.isNewerThan(getLastUpdateTime())) 461 { 462 lastUpdateTime = csn; 463 } 464 } 465 466 return true; 467 } 468 469 /** 470 * Process a add attribute values that is conflicting with a previous modification. 471 * 472 * @param csn 473 * the historical info associated to the entry 474 * @param m 475 * the modification that is being processed 476 * @return {@code true} if no conflict was detected, {@code false} otherwise. 477 */ 478 private boolean processAddConflict(CSN csn, Modification m) 479 { 480 /* 481 * if historicalattributedelete is newer forget this mod else find 482 * attr value if does not exist add historicalvalueadded timestamp 483 * add real value in entry else if timestamp older and already was 484 * historicalvalueadded update historicalvalueadded else if 485 * timestamp older and was historicalvaluedeleted change 486 * historicalvaluedeleted into historicalvalueadded add value in 487 * real entry 488 */ 489 490 if (csn.isOlderThan(getDeleteTime())) 491 { 492 /* A delete has been done more recently than this add 493 * forget this MOD ADD 494 */ 495 return false; 496 } 497 498 Attribute attribute = m.getAttribute(); 499 AttributeBuilder builder = new AttributeBuilder(attribute); 500 AttributeType attrType = attribute.getAttributeDescription().getAttributeType(); 501 for (ByteString addVal : attribute) 502 { 503 AttrValueHistorical valInfo = new AttrValueHistorical(addVal, attrType, csn, null); 504 AttrValueHistorical oldValInfo = valuesHist.get(valInfo); 505 if (oldValInfo == null) 506 { 507 /* this value does not exist yet 508 * add it in the historical information 509 * let the operation process normally 510 */ 511 valuesHist.add(valInfo); 512 } 513 else 514 { 515 if (oldValInfo.isUpdate()) 516 { 517 // if the value is already present check if the updateTime must be updated 518 if (csn.isNewerThan(oldValInfo.getValueUpdateTime())) 519 { 520 // replay the new value even though it is semantically the same as the value that's already in 521 // the entry. This is to handle cases where the client changes the case of a case ignore string, 522 // etc. The modify will succeed because we use the permissive modify control 523 valuesHist.addOrReplace(valInfo); 524 } 525 else 526 { 527 // don't replay the new value because it is older than the current value 528 builder.remove(addVal); 529 } 530 } 531 else 532 { // it is a delete 533 /* this value is marked as a deleted value 534 * check if this mod is more recent the this delete 535 */ 536 if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime())) 537 { 538 valuesHist.addOrReplace(valInfo); 539 } 540 else 541 { 542 /* the delete that is present in the historical information 543 * is more recent so it must win, 544 * remove this value from the list of values to add 545 * don't update the historical information 546 */ 547 builder.remove(addVal); 548 } 549 } 550 } 551 } 552 553 Attribute attr = builder.toAttribute(); 554 m.setAttribute(attr); 555 556 if (attr.isEmpty()) 557 { 558 return false; 559 } 560 561 if (csn.isNewerThan(getLastUpdateTime())) 562 { 563 lastUpdateTime = csn; 564 } 565 return true; 566 } 567 568 @Override 569 public void assign(HistAttrModificationKey histKey, AttributeType attrType, ByteString value, CSN csn) 570 { 571 switch (histKey) 572 { 573 case ADD: 574 if (value != null) 575 { 576 add(value, attrType, csn); 577 } 578 break; 579 580 case DEL: 581 if (value != null) 582 { 583 delete(value, attrType, csn); 584 } 585 break; 586 587 case REPL: 588 delete(csn); 589 if (value != null) 590 { 591 add(value, attrType, csn); 592 } 593 break; 594 595 case ATTRDEL: 596 delete(csn); 597 break; 598 } 599 } 600 601 @Override 602 public String toString() 603 { 604 final StringBuilder sb = new StringBuilder(); 605 sb.append(getClass().getSimpleName()).append("("); 606 boolean deleteAppended = false; 607 if (deleteTime != null) 608 { 609 deleteAppended = true; 610 sb.append("deleteTime=").append(deleteTime); 611 } 612 if (lastUpdateTime != null) 613 { 614 if (deleteAppended) 615 { 616 sb.append(", "); 617 } 618 sb.append("lastUpdateTime=").append(lastUpdateTime); 619 } 620 sb.append(", valuesHist=").append(valuesHist); 621 sb.append(")"); 622 return sb.toString(); 623 } 624}