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