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 2007-2008 Sun Microsystems, Inc.
026     */
027    package org.opends.server.replication.plugin;
028    
029    import java.util.NoSuchElementException;
030    import java.util.SortedMap;
031    import java.util.SortedSet;
032    import java.util.TreeMap;
033    import java.util.TreeSet;
034    
035    import org.opends.server.core.AddOperation;
036    import org.opends.server.core.DeleteOperation;
037    import org.opends.server.core.ModifyOperation;
038    import org.opends.server.replication.common.ChangeNumber;
039    import org.opends.server.replication.common.ChangeNumberGenerator;
040    import org.opends.server.replication.common.ServerState;
041    import org.opends.server.replication.protocol.AddMsg;
042    import org.opends.server.replication.protocol.DeleteMsg;
043    import org.opends.server.replication.protocol.ModifyDNMsg;
044    import org.opends.server.replication.protocol.OperationContext;
045    import org.opends.server.replication.protocol.UpdateMessage;
046    import org.opends.server.types.DN;
047    
048    /**
049     *
050     * This class is used to store the list of remote changes received
051     * from a replication server and taht are either currently being replayed
052     * or that are waiting for being replayed.
053     *
054     * It is used to know when the ServerState must be updated and to conpute
055     * the dependencies between operations.
056     *
057     * One of this object is instanciated for each ReplicationDomain.
058     *
059     */
060    public class RemotePendingChanges
061    {
062      /**
063       * A map used to store the pending changes.
064       */
065      private SortedMap<ChangeNumber, PendingChange> pendingChanges =
066        new TreeMap<ChangeNumber, PendingChange>();
067    
068      /**
069       * A sorted set containing the list of PendingChanges that have
070       * not been replayed correctly because they are dependent on
071       * another change to be completed.
072       */
073      private SortedSet<PendingChange> dependentChanges =
074        new TreeSet<PendingChange>();
075    
076      /**
077       * The ServerState that will be updated when UpdateMessage are fully replayed.
078       */
079      private ServerState state;
080    
081      /**
082       * The ChangeNumberGenerator to must be adjusted when new changes
083       * are received from a remote server.
084       */
085      private ChangeNumberGenerator changeNumberGenerator;
086    
087      /**
088       * Creates a new RemotePendingChanges using the provided ServerState.
089       *
090       * @param changeNumberGenerator The ChangeNumberGenerator that should
091       *                              be adjusted when changes are received.
092       * @param state   The ServerState that will be updated when UpdateMessage
093       *                have been fully replayed.
094       */
095      public RemotePendingChanges(ChangeNumberGenerator changeNumberGenerator,
096                                  ServerState state)
097      {
098        this.changeNumberGenerator = changeNumberGenerator;
099        this.state = state;
100      }
101    
102      /**
103       * Add a new UpdateMessage that was received from the replication server
104       * to the pendingList.
105       *
106       * @param update The UpdateMessage that was received from the replication
107       *               server and that will be added to the pending list.
108       */
109      public synchronized void putRemoteUpdate(UpdateMessage update)
110      {
111        ChangeNumber changeNumber = update.getChangeNumber();
112        changeNumberGenerator.adjust(changeNumber);
113        pendingChanges.put(changeNumber, new PendingChange(changeNumber, null,
114                                                            update));
115      }
116    
117      /**
118       * Mark an update message as committed.
119       *
120       * @param changeNumber The ChangeNumber of the update message that must be
121       *                     set as committed.
122       */
123      public synchronized void commit(ChangeNumber changeNumber)
124      {
125        PendingChange curChange = pendingChanges.get(changeNumber);
126        if (curChange == null)
127        {
128          throw new NoSuchElementException();
129        }
130        curChange.setCommitted(true);
131    
132        ChangeNumber firstChangeNumber = pendingChanges.firstKey();
133        PendingChange firstChange = pendingChanges.get(firstChangeNumber);
134    
135        while ((firstChange != null) && firstChange.isCommitted())
136        {
137          state.update(firstChangeNumber);
138          pendingChanges.remove(firstChangeNumber);
139    
140          if (pendingChanges.isEmpty())
141          {
142            firstChange = null;
143          }
144          else
145          {
146            firstChangeNumber = pendingChanges.firstKey();
147            firstChange = pendingChanges.get(firstChangeNumber);
148          }
149        }
150      }
151    
152      /**
153       * Get the first update in the list that have some dependencies cleared.
154       *
155       * @return The UpdateMessage to be handled.
156       */
157      public synchronized UpdateMessage getNextUpdate()
158      {
159        /*
160         * Parse the list of Update with dependencies and check if the dependencies
161         * are now cleared until an Update without dependencies is found.
162         */
163        for (PendingChange change : dependentChanges)
164        {
165          if (change.dependenciesIsCovered(state))
166          {
167            dependentChanges.remove(change);
168            return change.getMsg();
169          }
170        }
171        return null;
172      }
173    
174      /**
175       * Mark the first pendingChange as dependent on the second PendingChange.
176       * @param dependentChange The PendingChange that depend on the second
177       *                        PendingChange.
178       * @param pendingChange   The PendingChange on which the first PendingChange
179       *                        is dependent.
180       */
181      private void addDependency(
182          PendingChange dependentChange, PendingChange pendingChange)
183      {
184        dependentChange.addDependency(pendingChange.getChangeNumber());
185        dependentChanges.add(dependentChange);
186      }
187    
188      /**
189       * Check if the given AddOperation has some dependencies on any
190       * currently running previous operation.
191       * Update the dependency list in the associated PendingChange if
192       * there are some dependencies.
193       * AddOperation depends on
194       *
195       * - DeleteOperation done on the same DN
196       * - ModifyDnOperation with the same target DN as the ADD DN
197       * - ModifyDnOperation with new DN equals to the ADD DN parent
198       * - AddOperation done on the parent DN of the ADD DN
199       *
200       * @param op The AddOperation to be checked.
201       *
202       * @return A boolean indicating if this operation has some dependencies.
203       */
204      public synchronized boolean checkDependencies(AddOperation op)
205      {
206        boolean hasDependencies = false;
207        DN targetDn = op.getEntryDN();
208        ChangeNumber changeNumber = OperationContext.getChangeNumber(op);
209        PendingChange change = pendingChanges.get(changeNumber);
210        if (change == null)
211          return false;
212    
213        for (PendingChange pendingChange : pendingChanges.values())
214        {
215          if (pendingChange.getChangeNumber().older(changeNumber))
216          {
217            UpdateMessage pendingMsg = pendingChange.getMsg();
218            if (pendingMsg != null)
219            {
220              if (pendingMsg instanceof DeleteMsg)
221              {
222                /*
223                 * Check is the operation to be run is a deleteOperation on the
224                 * same DN.
225                 */
226                if (pendingChange.getTargetDN().equals(targetDn))
227                {
228                  hasDependencies = true;
229                  addDependency(change, pendingChange);
230                }
231              }
232              else if (pendingMsg instanceof AddMsg)
233              {
234                /*
235                 * Check if the operation to be run is an addOperation on a
236                 * parent of the current AddOperation.
237                 */
238                if (pendingChange.getTargetDN().isAncestorOf(targetDn))
239                {
240                  hasDependencies = true;
241                  addDependency(change, pendingChange);
242                }
243              }
244              else if (pendingMsg instanceof ModifyDNMsg)
245              {
246                /*
247                 * Check if the operation to be run is ModifyDnOperation with
248                 * the same target DN as the ADD DN
249                 * or a ModifyDnOperation with new DN equals to the ADD DN parent
250                 */
251                if (pendingChange.getTargetDN().equals(targetDn))
252                {
253                  hasDependencies = true;
254                  addDependency(change, pendingChange);
255                }
256                else
257                {
258                  ModifyDNMsg pendingModDn = (ModifyDNMsg) pendingChange.getMsg();
259                  if (pendingModDn.newDNIsParent(targetDn))
260                  {
261                    hasDependencies = true;
262                    addDependency(change, pendingChange);
263                  }
264                }
265              }
266            }
267          }
268        }
269        return hasDependencies;
270      }
271    
272      /**
273       * Check if the given ModifyOperation has some dependencies on any
274       * currently running previous operation.
275       * Update the dependency list in the associated PendingChange if
276       * there are some dependencies.
277       *
278       * ModifyOperation depends on
279       * - AddOperation done on the same DN
280       *
281       * @param op The ModifyOperation to be checked.
282       *
283       * @return A boolean indicating if this operation has some dependencies.
284       */
285      public synchronized boolean checkDependencies(ModifyOperation op)
286      {
287        boolean hasDependencies = false;
288        DN targetDn = op.getEntryDN();
289        ChangeNumber changeNumber = OperationContext.getChangeNumber(op);
290        PendingChange change = pendingChanges.get(changeNumber);
291        if (change == null)
292          return false;
293    
294        for (PendingChange pendingChange : pendingChanges.values())
295        {
296          if (pendingChange.getChangeNumber().older(changeNumber))
297          {
298            UpdateMessage pendingMsg = pendingChange.getMsg();
299            if (pendingMsg != null)
300            {
301              if (pendingMsg instanceof AddMsg)
302              {
303                /*
304                 * Check if the operation to be run is an addOperation on a
305                 * same DN.
306                 */
307                if (pendingChange.getTargetDN().equals(targetDn))
308                {
309                  hasDependencies = true;
310                  addDependency(change, pendingChange);
311                }
312              }
313            }
314          }
315        }
316        return hasDependencies;
317      }
318    
319      /**
320       * Check if the given ModifyDNMsg has some dependencies on any
321       * currently running previous operation.
322       * Update the dependency list in the associated PendingChange if
323       * there are some dependencies.
324       *
325       * Modify DN Operation depends on
326       * - AddOperation done on the same DN as the target DN of the MODDN operation
327       * - AddOperation done on the new parent of the MODDN  operation
328       * - DeleteOperation done on the new DN of the MODDN operation
329       * - ModifyDNOperation done from the new DN of the MODDN operation
330       *
331       * @param msg The ModifyDNMsg to be checked.
332       *
333       * @return A boolean indicating if this operation has some dependencies.
334       */
335      public synchronized boolean checkDependencies(ModifyDNMsg msg)
336      {
337        boolean hasDependencies = false;
338        ChangeNumber changeNumber = msg.getChangeNumber();
339        PendingChange change = pendingChanges.get(changeNumber);
340        if (change == null)
341          return false;
342    
343        DN targetDn = change.getTargetDN();
344    
345    
346        for (PendingChange pendingChange : pendingChanges.values())
347        {
348          if (pendingChange.getChangeNumber().older(changeNumber))
349          {
350            UpdateMessage pendingMsg = pendingChange.getMsg();
351            if (pendingMsg != null)
352            {
353              if (pendingMsg instanceof DeleteMsg)
354              {
355                // Check if the target of the Delete is the same
356                // as the new DN of this ModifyDN
357                if (msg.newDNIsEqual(pendingChange.getTargetDN()))
358                {
359                  hasDependencies = true;
360                  addDependency(change, pendingChange);
361                }
362              }
363              else if (pendingMsg instanceof AddMsg)
364              {
365                // Check if the Add Operation was done on the new parent of
366                // the MODDN  operation
367                if (msg.newParentIsEqual(pendingChange.getTargetDN()))
368                {
369                  hasDependencies = true;
370                  addDependency(change, pendingChange);
371                }
372                // Check if the AddOperation was done on the same DN as the
373                // target DN of the MODDN operation
374                if (pendingChange.getTargetDN().equals(targetDn))
375                {
376                  hasDependencies = true;
377                  addDependency(change, pendingChange);
378                }
379              }
380              else if (pendingMsg instanceof ModifyDNMsg)
381              {
382                // Check if the ModifyDNOperation was done from the new DN of
383                // the MODDN operation
384                if (msg.newDNIsEqual(pendingChange.getTargetDN()))
385                {
386                  hasDependencies = true;
387                  addDependency(change, pendingChange);
388                }
389              }
390            }
391          }
392        }
393        return hasDependencies;
394      }
395    
396      /**
397       * Check if the given DeleteOperation has some dependencies on any
398       * currently running previous operation.
399       * Update the dependency list in the associated PendingChange if
400       * there are some dependencies.
401       *
402       * DeleteOperation depends on
403       * - DeleteOperation done on children DN
404       * - ModifyDnOperation with target DN that are children of the DEL DN
405       * - AddOperation done on the same DN
406       *
407       *
408       * @param op The DeleteOperation to be checked.
409       *
410       * @return A boolean indicating if this operation has some dependencies.
411       */
412      public synchronized boolean checkDependencies(DeleteOperation op)
413      {
414        boolean hasDependencies = false;
415        DN targetDn = op.getEntryDN();
416        ChangeNumber changeNumber = OperationContext.getChangeNumber(op);
417        PendingChange change = pendingChanges.get(changeNumber);
418        if (change == null)
419          return false;
420    
421        for (PendingChange pendingChange : pendingChanges.values())
422        {
423          if (pendingChange.getChangeNumber().older(changeNumber))
424          {
425            UpdateMessage pendingMsg = pendingChange.getMsg();
426            if (pendingMsg != null)
427            {
428              if (pendingMsg instanceof DeleteMsg)
429              {
430                /*
431                 * Check if the operation to be run is a deleteOperation on a
432                 * children of the current DeleteOperation.
433                 */
434                if (pendingChange.getTargetDN().isDescendantOf(targetDn))
435                {
436                  hasDependencies = true;
437                  addDependency(change, pendingChange);
438                }
439              }
440              else if (pendingMsg instanceof AddMsg)
441              {
442                /*
443                 * Check if the operation to be run is an addOperation on a
444                 * parent of the current DeleteOperation.
445                 */
446                if (pendingChange.getTargetDN().equals(targetDn))
447                {
448                  hasDependencies = true;
449                  addDependency(change, pendingChange);
450                }
451              }
452              else if (pendingMsg instanceof ModifyDNMsg)
453              {
454                ModifyDNMsg pendingModDn = (ModifyDNMsg) pendingChange.getMsg();
455                /*
456                 * Check if the operation to be run is an ModifyDNOperation
457                 * on a children of the current DeleteOperation
458                 */
459                if ((pendingChange.getTargetDN().isDescendantOf(targetDn)) ||
460                    (pendingModDn.newDNIsParent(targetDn)))
461                {
462                  hasDependencies = true;
463                  addDependency(change, pendingChange);
464                }
465              }
466            }
467          }
468        }
469        return hasDependencies;
470      }
471    }