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 }