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