HDFS-13252. Code refactoring: Remove Diff.ListType.
[hadoop.git] / hadoop-hdfs-project / hadoop-hdfs / src / main / java / org / apache / hadoop / hdfs / server / namenode / snapshot / DirectoryWithSnapshotFeature.java
1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18 package org.apache.hadoop.hdfs.server.namenode.snapshot;
19
20 import com.google.common.base.Preconditions;
21 import org.apache.hadoop.classification.InterfaceAudience;
22 import org.apache.hadoop.hdfs.protocol.QuotaExceededException;
23 import org.apache.hadoop.hdfs.server.blockmanagement.BlockStoragePolicySuite;
24 import org.apache.hadoop.hdfs.server.namenode.*;
25 import org.apache.hadoop.hdfs.server.namenode.snapshot.SnapshotFSImageFormat.ReferenceMap;
26 import org.apache.hadoop.hdfs.util.Diff;
27 import org.apache.hadoop.hdfs.util.Diff.Container;
28 import org.apache.hadoop.hdfs.util.Diff.UndoInfo;
29 import org.apache.hadoop.hdfs.util.ReadOnlyList;
30 import org.apache.hadoop.security.AccessControlException;
31
32 import java.io.DataOutput;
33 import java.io.IOException;
34 import java.util.*;
35
36 import static org.apache.hadoop.hdfs.server.namenode.snapshot.Snapshot.NO_SNAPSHOT_ID;
37
38 /**
39 * Feature used to store and process the snapshot diff information for a
40 * directory. In particular, it contains a directory diff list recording changes
41 * made to the directory and its children for each snapshot.
42 */
43 @InterfaceAudience.Private
44 public class DirectoryWithSnapshotFeature implements INode.Feature {
45 /**
46 * The difference between the current state and a previous snapshot
47 * of the children list of an INodeDirectory.
48 */
49 static class ChildrenDiff extends Diff<byte[], INode> {
50 ChildrenDiff() {}
51
52 private ChildrenDiff(final List<INode> created, final List<INode> deleted) {
53 super(created, deleted);
54 }
55
56 /**
57 * Replace the given child from the created list.
58 * @return true if the child is replaced; false if the child is not found.
59 */
60 private boolean replaceCreated(final INode oldChild, final INode newChild) {
61 final List<INode> list = getCreatedUnmodifiable();
62 final int i = search(list, oldChild.getLocalNameBytes());
63 if (i < 0 || list.get(i).getId() != oldChild.getId()) {
64 return false;
65 }
66
67 final INode removed = setCreated(i, newChild);
68 Preconditions.checkState(removed == oldChild);
69 return true;
70 }
71
72 /** clear the created list */
73 private void destroyCreatedList(INode.ReclaimContext reclaimContext,
74 final INodeDirectory currentINode) {
75 for (INode c : getCreatedUnmodifiable()) {
76 c.destroyAndCollectBlocks(reclaimContext);
77 // c should be contained in the children list, remove it
78 currentINode.removeChild(c);
79 }
80 clearCreated();
81 }
82
83 /** clear the deleted list */
84 private void destroyDeletedList(INode.ReclaimContext reclaimContext) {
85 for (INode d : getDeletedUnmodifiable()) {
86 d.destroyAndCollectBlocks(reclaimContext);
87 }
88 clearDeleted();
89 }
90
91 /** Serialize {@link #created} */
92 private void writeCreated(DataOutput out) throws IOException {
93 final List<INode> created = getCreatedUnmodifiable();
94 out.writeInt(created.size());
95 for (INode node : created) {
96 // For INode in created list, we only need to record its local name
97 byte[] name = node.getLocalNameBytes();
98 out.writeShort(name.length);
99 out.write(name);
100 }
101 }
102
103 /** Serialize {@link #deleted} */
104 private void writeDeleted(DataOutput out,
105 ReferenceMap referenceMap) throws IOException {
106 final List<INode> deleted = getDeletedUnmodifiable();
107 out.writeInt(deleted.size());
108 for (INode node : deleted) {
109 FSImageSerialization.saveINode2Image(node, out, true, referenceMap);
110 }
111 }
112
113 /** Serialize to out */
114 private void write(DataOutput out, ReferenceMap referenceMap
115 ) throws IOException {
116 writeCreated(out);
117 writeDeleted(out, referenceMap);
118 }
119
120 /** Get the list of INodeDirectory contained in the deleted list */
121 private void getDirsInDeleted(List<INodeDirectory> dirList) {
122 for (INode node : getDeletedUnmodifiable()) {
123 if (node.isDirectory()) {
124 dirList.add(node.asDirectory());
125 }
126 }
127 }
128 }
129
130 /**
131 * The difference of an {@link INodeDirectory} between two snapshots.
132 */
133 public static class DirectoryDiff extends
134 AbstractINodeDiff<INodeDirectory, INodeDirectoryAttributes, DirectoryDiff> {
135 /** The size of the children list at snapshot creation time. */
136 private final int childrenSize;
137 /** The children list diff. */
138 private final ChildrenDiff diff;
139 private boolean isSnapshotRoot = false;
140
141 private DirectoryDiff(int snapshotId, INodeDirectory dir) {
142 this(snapshotId, dir, new ChildrenDiff());
143 }
144
145 public DirectoryDiff(int snapshotId, INodeDirectory dir,
146 ChildrenDiff diff) {
147 super(snapshotId, null, null);
148 this.childrenSize = dir.getChildrenList(Snapshot.CURRENT_STATE_ID).size();
149 this.diff = diff;
150 }
151 /** Constructor used by FSImage loading */
152 DirectoryDiff(int snapshotId, INodeDirectoryAttributes snapshotINode,
153 DirectoryDiff posteriorDiff, int childrenSize, List<INode> createdList,
154 List<INode> deletedList, boolean isSnapshotRoot) {
155 super(snapshotId, snapshotINode, posteriorDiff);
156 this.childrenSize = childrenSize;
157 this.diff = new ChildrenDiff(createdList, deletedList);
158 this.isSnapshotRoot = isSnapshotRoot;
159 }
160
161 public ChildrenDiff getChildrenDiff() {
162 return diff;
163 }
164
165 void setSnapshotRoot(INodeDirectoryAttributes root) {
166 this.snapshotINode = root;
167 this.isSnapshotRoot = true;
168 }
169
170 boolean isSnapshotRoot() {
171 return isSnapshotRoot;
172 }
173
174 @Override
175 void combinePosteriorAndCollectBlocks(
176 final INode.ReclaimContext reclaimContext,
177 final INodeDirectory currentDir,
178 final DirectoryDiff posterior) {
179 diff.combinePosterior(posterior.diff, new Diff.Processor<INode>() {
180 /** Collect blocks for deleted files. */
181 @Override
182 public void process(INode inode) {
183 if (inode != null) {
184 inode.destroyAndCollectBlocks(reclaimContext);
185 }
186 }
187 });
188 }
189
190 /**
191 * @return The children list of a directory in a snapshot.
192 * Since the snapshot is read-only, the logical view of the list is
193 * never changed although the internal data structure may mutate.
194 */
195 private ReadOnlyList<INode> getChildrenList(final INodeDirectory currentDir) {
196 return new ReadOnlyList<INode>() {
197 private List<INode> children = null;
198
199 private List<INode> initChildren() {
200 if (children == null) {
201 final ChildrenDiff combined = new ChildrenDiff();
202 DirectoryDiffList directoryDiffList =
203 currentDir.getDirectoryWithSnapshotFeature().diffs;
204 final int diffIndex =
205 directoryDiffList.getDiffIndexById(getSnapshotId());
206 List<DirectoryDiff> diffList = directoryDiffList
207 .getDiffListBetweenSnapshots(diffIndex,
208 directoryDiffList.asList().size(), currentDir);
209 for (DirectoryDiff d : diffList) {
210 combined.combinePosterior(d.diff, null);
211 }
212 children = combined.apply2Current(ReadOnlyList.Util
213 .asList(currentDir.getChildrenList(Snapshot.CURRENT_STATE_ID)));
214 }
215 return children;
216 }
217
218 @Override
219 public Iterator<INode> iterator() {
220 return initChildren().iterator();
221 }
222
223 @Override
224 public boolean isEmpty() {
225 return childrenSize == 0;
226 }
227
228 @Override
229 public int size() {
230 return childrenSize;
231 }
232
233 @Override
234 public INode get(int i) {
235 return initChildren().get(i);
236 }
237 };
238 }
239
240 /** @return the child with the given name. */
241 INode getChild(byte[] name, boolean checkPosterior,
242 INodeDirectory currentDir) {
243 for(DirectoryDiff d = this; ; d = d.getPosterior()) {
244 final Container<INode> returned = d.diff.accessPrevious(name);
245 if (returned != null) {
246 // the diff is able to determine the inode
247 return returned.getElement();
248 } else if (!checkPosterior) {
249 // Since checkPosterior is false, return null, i.e. not found.
250 return null;
251 } else if (d.getPosterior() == null) {
252 // no more posterior diff, get from current inode.
253 return currentDir.getChild(name, Snapshot.CURRENT_STATE_ID);
254 }
255 }
256 }
257
258 @Override
259 public String toString() {
260 return super.toString() + " childrenSize=" + childrenSize + ", " + diff;
261 }
262
263 int getChildrenSize() {
264 return childrenSize;
265 }
266
267 @Override
268 void write(DataOutput out, ReferenceMap referenceMap) throws IOException {
269 writeSnapshot(out);
270 out.writeInt(childrenSize);
271
272 // Write snapshotINode
273 out.writeBoolean(isSnapshotRoot);
274 if (!isSnapshotRoot) {
275 if (snapshotINode != null) {
276 out.writeBoolean(true);
277 FSImageSerialization.writeINodeDirectoryAttributes(snapshotINode, out);
278 } else {
279 out.writeBoolean(false);
280 }
281 }
282 // Write diff. Node need to write poseriorDiff, since diffs is a list.
283 diff.write(out, referenceMap);
284 }
285
286 @Override
287 void destroyDiffAndCollectBlocks(
288 INode.ReclaimContext reclaimContext, INodeDirectory currentINode) {
289 // this diff has been deleted
290 diff.destroyDeletedList(reclaimContext);
291 INodeDirectoryAttributes snapshotINode = getSnapshotINode();
292 if (snapshotINode != null && snapshotINode.getAclFeature() != null) {
293 AclStorage.removeAclFeature(snapshotINode.getAclFeature());
294 }
295 }
296 }
297
298 /** A list of directory diffs. */
299 public static class DirectoryDiffList
300 extends AbstractINodeDiffList<INodeDirectory, INodeDirectoryAttributes, DirectoryDiff> {
301
302 @Override
303 DirectoryDiff createDiff(int snapshot, INodeDirectory currentDir) {
304 return new DirectoryDiff(snapshot, currentDir);
305 }
306
307 @Override
308 INodeDirectoryAttributes createSnapshotCopy(INodeDirectory currentDir) {
309 return currentDir.isQuotaSet()?
310 new INodeDirectoryAttributes.CopyWithQuota(currentDir)
311 : new INodeDirectoryAttributes.SnapshotCopy(currentDir);
312 }
313
314 @Override
315 DiffList<DirectoryDiff> newDiffs() {
316 return DirectoryDiffListFactory
317 .createDiffList(INodeDirectory.DEFAULT_FILES_PER_DIRECTORY);
318 }
319
320 /** Replace the given child in the created/deleted list, if there is any. */
321 public boolean replaceCreatedChild(final INode oldChild,
322 final INode newChild) {
323 final DiffList<DirectoryDiff> diffList = asList();
324 for(int i = diffList.size() - 1; i >= 0; i--) {
325 final ChildrenDiff diff = diffList.get(i).diff;
326 if (diff.replaceCreated(oldChild, newChild)) {
327 return true;
328 }
329 }
330 return false;
331 }
332
333 /** Remove the given child from the deleted list, if there is any. */
334 public boolean removeDeletedChild(final INode child) {
335 final DiffList<DirectoryDiff> diffList = asList();
336 for(int i = diffList.size() - 1; i >= 0; i--) {
337 final ChildrenDiff diff = diffList.get(i).diff;
338 if (diff.removeDeleted(child)) {
339 return true;
340 }
341 }
342 return false;
343 }
344
345 /**
346 * Find the corresponding snapshot whose deleted list contains the given
347 * inode.
348 * @return the id of the snapshot. {@link Snapshot#NO_SNAPSHOT_ID} if the
349 * given inode is not in any of the snapshot.
350 */
351 public int findSnapshotDeleted(final INode child) {
352 final DiffList<DirectoryDiff> diffList = asList();
353 for(int i = diffList.size() - 1; i >= 0; i--) {
354 final DirectoryDiff diff = diffList.get(i);
355 if (diff.getChildrenDiff().containsDeleted(child)) {
356 return diff.getSnapshotId();
357 }
358 }
359 return NO_SNAPSHOT_ID;
360 }
361
362 /**
363 * Returns the list of diffs between two indexes corresponding to two
364 * snapshots.
365 * @param fromIndex Index of the diff corresponding to the earlier snapshot
366 * @param toIndex Index of the diff corresponding to the later snapshot
367 * @param dir The Directory to which the diffList belongs
368 * @return list of directory diffs
369 */
370 List<DirectoryDiff> getDiffListBetweenSnapshots(int fromIndex, int toIndex,
371 INodeDirectory dir) {
372 return asList().getMinListForRange(fromIndex, toIndex, dir);
373 }
374 }
375
376 private static Map<INode, INode> cloneDiffList(List<INode> diffList) {
377 if (diffList == null || diffList.size() == 0) {
378 return null;
379 }
380 Map<INode, INode> map = new HashMap<>(diffList.size());
381 for (INode node : diffList) {
382 map.put(node, node);
383 }
384 return map;
385 }
386
387 /**
388 * Destroy a subtree under a DstReference node.
389 */
390 public static void destroyDstSubtree(INode.ReclaimContext reclaimContext,
391 INode inode, final int snapshot, final int prior) {
392 Preconditions.checkArgument(prior != NO_SNAPSHOT_ID);
393 if (inode.isReference()) {
394 if (inode instanceof INodeReference.WithName
395 && snapshot != Snapshot.CURRENT_STATE_ID) {
396 // this inode has been renamed before the deletion of the DstReference
397 // subtree
398 inode.cleanSubtree(reclaimContext, snapshot, prior);
399 } else {
400 // for DstReference node, continue this process to its subtree
401 destroyDstSubtree(reclaimContext,
402 inode.asReference().getReferredINode(), snapshot, prior);
403 }
404 } else if (inode.isFile()) {
405 inode.cleanSubtree(reclaimContext, snapshot, prior);
406 } else if (inode.isDirectory()) {
407 Map<INode, INode> excludedNodes = null;
408 INodeDirectory dir = inode.asDirectory();
409 DirectoryWithSnapshotFeature sf = dir.getDirectoryWithSnapshotFeature();
410 if (sf != null) {
411 DirectoryDiffList diffList = sf.getDiffs();
412 DirectoryDiff priorDiff = diffList.getDiffById(prior);
413 if (priorDiff != null && priorDiff.getSnapshotId() == prior) {
414 List<INode> dList = priorDiff.diff.getDeletedUnmodifiable();
415 excludedNodes = cloneDiffList(dList);
416 }
417
418 if (snapshot != Snapshot.CURRENT_STATE_ID) {
419 diffList.deleteSnapshotDiff(reclaimContext,
420 snapshot, prior, dir);
421 }
422 priorDiff = diffList.getDiffById(prior);
423 if (priorDiff != null && priorDiff.getSnapshotId() == prior) {
424 priorDiff.diff.destroyCreatedList(reclaimContext, dir);
425 }
426 }
427 for (INode child : inode.asDirectory().getChildrenList(prior)) {
428 if (excludedNodes != null && excludedNodes.containsKey(child)) {
429 continue;
430 }
431 destroyDstSubtree(reclaimContext, child, snapshot, prior);
432 }
433 }
434 }
435
436 /**
437 * Clean an inode while we move it from the deleted list of post to the
438 * deleted list of prior.
439 * @param reclaimContext blocks and inodes that need to be reclaimed
440 * @param inode The inode to clean.
441 * @param post The post snapshot.
442 * @param prior The id of the prior snapshot.
443 */
444 private static void cleanDeletedINode(INode.ReclaimContext reclaimContext,
445 INode inode, final int post, final int prior) {
446 Deque<INode> queue = new ArrayDeque<>();
447 queue.addLast(inode);
448 while (!queue.isEmpty()) {
449 INode topNode = queue.pollFirst();
450 if (topNode instanceof INodeReference.WithName) {
451 INodeReference.WithName wn = (INodeReference.WithName) topNode;
452 if (wn.getLastSnapshotId() >= post) {
453 INodeReference.WithCount wc =
454 (INodeReference.WithCount) wn.getReferredINode();
455 if (wc.getLastWithName() == wn && wc.getParentReference() == null) {
456 // this wn is the last wn inside of the wc, also the dstRef node has
457 // been deleted. In this case, we should treat the referred file/dir
458 // as normal case
459 queue.add(wc.getReferredINode());
460 } else {
461 wn.cleanSubtree(reclaimContext, post, prior);
462 }
463 }
464 // For DstReference node, since the node is not in the created list of
465 // prior, we should treat it as regular file/dir
466 } else if (topNode.isFile() && topNode.asFile().isWithSnapshot()) {
467 INodeFile file = topNode.asFile();
468 file.getDiffs().deleteSnapshotDiff(reclaimContext, post, prior, file);
469 } else if (topNode.isDirectory()) {
470 INodeDirectory dir = topNode.asDirectory();
471 ChildrenDiff priorChildrenDiff = null;
472 DirectoryWithSnapshotFeature sf = dir.getDirectoryWithSnapshotFeature();
473 if (sf != null) {
474 // delete files/dirs created after prior. Note that these
475 // files/dirs, along with inode, were deleted right after post.
476 DirectoryDiff priorDiff = sf.getDiffs().getDiffById(prior);
477 if (priorDiff != null && priorDiff.getSnapshotId() == prior) {
478 priorChildrenDiff = priorDiff.getChildrenDiff();
479 priorChildrenDiff.destroyCreatedList(reclaimContext, dir);
480 }
481 }
482
483 for (INode child : dir.getChildrenList(prior)) {
484 if (priorChildrenDiff != null && priorChildrenDiff.getDeleted(
485 child.getLocalNameBytes()) != null) {
486 continue;
487 }
488 queue.addLast(child);
489 }
490 }
491 }
492 }
493
494 /** Diff list sorted by snapshot IDs, i.e. in chronological order. */
495 private final DirectoryDiffList diffs;
496
497 public DirectoryWithSnapshotFeature(DirectoryDiffList diffs) {
498 this.diffs = diffs != null ? diffs : new DirectoryDiffList();
499 }
500
501 /** @return the last snapshot. */
502 public int getLastSnapshotId() {
503 return diffs.getLastSnapshotId();
504 }
505
506 /** @return the snapshot diff list. */
507 public DirectoryDiffList getDiffs() {
508 return diffs;
509 }
510
511 /**
512 * Get all the directories that are stored in some snapshot but not in the
513 * current children list. These directories are equivalent to the directories
514 * stored in the deletes lists.
515 */
516 public void getSnapshotDirectory(List<INodeDirectory> snapshotDir) {
517 for (DirectoryDiff sdiff : diffs) {
518 sdiff.getChildrenDiff().getDirsInDeleted(snapshotDir);
519 }
520 }
521
522 /**
523 * Add an inode into parent's children list. The caller of this method needs
524 * to make sure that parent is in the given snapshot "latest".
525 */
526 public boolean addChild(INodeDirectory parent, INode inode,
527 boolean setModTime, int latestSnapshotId) throws QuotaExceededException {
528 ChildrenDiff diff = diffs.checkAndAddLatestSnapshotDiff(latestSnapshotId,
529 parent).diff;
530 final int undoInfo = diff.create(inode);
531 boolean added = false;
532 try {
533 added = parent.addChild(inode, setModTime, Snapshot.CURRENT_STATE_ID);
534 } finally {
535 if (!added) {
536 diff.undoCreate(inode, undoInfo);
537 }
538 }
539 return added;
540 }
541
542 /**
543 * Remove an inode from parent's children list. The caller of this method
544 * needs to make sure that parent is in the given snapshot "latest".
545 */
546 public boolean removeChild(INodeDirectory parent, INode child,
547 int latestSnapshotId) {
548 // For a directory that is not a renamed node, if isInLatestSnapshot returns
549 // false, the directory is not in the latest snapshot, thus we do not need
550 // to record the removed child in any snapshot.
551 // For a directory that was moved/renamed, note that if the directory is in
552 // any of the previous snapshots, we will create a reference node for the
553 // directory while rename, and isInLatestSnapshot will return true in that
554 // scenario (if all previous snapshots have been deleted, isInLatestSnapshot
555 // still returns false). Thus if isInLatestSnapshot returns false, the
556 // directory node cannot be in any snapshot (not in current tree, nor in
557 // previous src tree). Thus we do not need to record the removed child in
558 // any snapshot.
559 ChildrenDiff diff = diffs.checkAndAddLatestSnapshotDiff(latestSnapshotId,
560 parent).diff;
561 final UndoInfo<INode> undoInfo = diff.delete(child);
562 boolean removed = false;
563 try {
564 removed = parent.removeChild(child);
565 } finally {
566 if (!removed) {
567 diff.undoDelete(child, undoInfo);
568 }
569 }
570 return removed;
571 }
572
573 /**
574 * @return If there is no corresponding directory diff for the given
575 * snapshot, this means that the current children list should be
576 * returned for the snapshot. Otherwise we calculate the children list
577 * for the snapshot and return it.
578 */
579 public ReadOnlyList<INode> getChildrenList(INodeDirectory currentINode,
580 final int snapshotId) {
581 final DirectoryDiff diff = diffs.getDiffById(snapshotId);
582 return diff != null ? diff.getChildrenList(currentINode) : currentINode
583 .getChildrenList(Snapshot.CURRENT_STATE_ID);
584 }
585
586 public INode getChild(INodeDirectory currentINode, byte[] name,
587 int snapshotId) {
588 final DirectoryDiff diff = diffs.getDiffById(snapshotId);
589 return diff != null ? diff.getChild(name, true, currentINode)
590 : currentINode.getChild(name, Snapshot.CURRENT_STATE_ID);
591 }
592
593 /** Used to record the modification of a symlink node */
594 public INode saveChild2Snapshot(INodeDirectory currentINode,
595 final INode child, final int latestSnapshotId, final INode snapshotCopy) {
596 Preconditions.checkArgument(!child.isDirectory(),
597 "child is a directory, child=%s", child);
598 Preconditions.checkArgument(latestSnapshotId != Snapshot.CURRENT_STATE_ID);
599
600 final DirectoryDiff diff = diffs.checkAndAddLatestSnapshotDiff(
601 latestSnapshotId, currentINode);
602 if (diff.getChild(child.getLocalNameBytes(), false, currentINode) != null) {
603 // it was already saved in the latest snapshot earlier.
604 return child;
605 }
606
607 diff.diff.modify(snapshotCopy, child);
608 return child;
609 }
610
611 public void clear(
612 INode.ReclaimContext reclaimContext, INodeDirectory currentINode) {
613 // destroy its diff list
614 for (DirectoryDiff diff : diffs) {
615 diff.destroyDiffAndCollectBlocks(reclaimContext, currentINode);
616 }
617 diffs.clear();
618 }
619
620 public QuotaCounts computeQuotaUsage4CurrentDirectory(
621 BlockStoragePolicySuite bsps, byte storagePolicyId) {
622 final QuotaCounts counts = new QuotaCounts.Builder().build();
623 for(DirectoryDiff d : diffs) {
624 for(INode deleted : d.getChildrenDiff().getDeletedUnmodifiable()) {
625 final byte childPolicyId = deleted.getStoragePolicyIDForQuota(
626 storagePolicyId);
627 counts.add(deleted.computeQuotaUsage(bsps, childPolicyId, false,
628 Snapshot.CURRENT_STATE_ID));
629 }
630 }
631 return counts;
632 }
633
634 public void computeContentSummary4Snapshot(final BlockStoragePolicySuite bsps,
635 final ContentCounts counts) throws AccessControlException {
636 // Create a new blank summary context for blocking processing of subtree.
637 ContentSummaryComputationContext summary =
638 new ContentSummaryComputationContext(bsps);
639 for(DirectoryDiff d : diffs) {
640 for(INode deleted : d.getChildrenDiff().getDeletedUnmodifiable()) {
641 deleted.computeContentSummary(Snapshot.CURRENT_STATE_ID, summary);
642 }
643 }
644 // Add the counts from deleted trees.
645 counts.addContents(summary.getCounts());
646 }
647
648 /**
649 * Compute the difference between Snapshots.
650 *
651 * @param fromSnapshot Start point of the diff computation. Null indicates
652 * current tree.
653 * @param toSnapshot End point of the diff computation. Null indicates current
654 * tree.
655 * @param diff Used to capture the changes happening to the children. Note
656 * that the diff still represents (later_snapshot - earlier_snapshot)
657 * although toSnapshot can be before fromSnapshot.
658 * @param currentINode The {@link INodeDirectory} this feature belongs to.
659 * @return Whether changes happened between the startSnapshot and endSnaphsot.
660 */
661 boolean computeDiffBetweenSnapshots(Snapshot fromSnapshot,
662 Snapshot toSnapshot, ChildrenDiff diff, INodeDirectory currentINode) {
663 int[] diffIndexPair = diffs.changedBetweenSnapshots(fromSnapshot,
664 toSnapshot);
665 if (diffIndexPair == null) {
666 return false;
667 }
668 int earlierDiffIndex = diffIndexPair[0];
669 int laterDiffIndex = diffIndexPair[1];
670
671 boolean dirMetadataChanged = false;
672 INodeDirectoryAttributes dirCopy = null;
673 List<DirectoryDiff> difflist = diffs
674 .getDiffListBetweenSnapshots(earlierDiffIndex, laterDiffIndex,
675 currentINode);
676 for (DirectoryDiff sdiff : difflist) {
677 diff.combinePosterior(sdiff.diff, null);
678 if (!dirMetadataChanged && sdiff.snapshotINode != null) {
679 if (dirCopy == null) {
680 dirCopy = sdiff.snapshotINode;
681 } else if (!dirCopy.metadataEquals(sdiff.snapshotINode)) {
682 dirMetadataChanged = true;
683 }
684 }
685 }
686
687 if (!diff.isEmpty() || dirMetadataChanged) {
688 return true;
689 } else if (dirCopy != null) {
690 for (int i = laterDiffIndex; i < difflist.size(); i++) {
691 if (!dirCopy.metadataEquals(difflist.get(i).snapshotINode)) {
692 return true;
693 }
694 }
695 return !dirCopy.metadataEquals(currentINode);
696 } else {
697 return false;
698 }
699 }
700
701 public void cleanDirectory(INode.ReclaimContext reclaimContext,
702 final INodeDirectory currentINode, final int snapshot, int prior) {
703 Map<INode, INode> priorCreated = null;
704 Map<INode, INode> priorDeleted = null;
705 QuotaCounts old = reclaimContext.quotaDelta().getCountsCopy();
706 if (snapshot == Snapshot.CURRENT_STATE_ID) { // delete the current directory
707 currentINode.recordModification(prior);
708 // delete everything in created list
709 DirectoryDiff lastDiff = diffs.getLast();
710 if (lastDiff != null) {
711 lastDiff.diff.destroyCreatedList(reclaimContext, currentINode);
712 }
713 currentINode.cleanSubtreeRecursively(reclaimContext, snapshot, prior,
714 null);
715 } else {
716 // update prior
717 prior = getDiffs().updatePrior(snapshot, prior);
718 // if there is a snapshot diff associated with prior, we need to record
719 // its original created and deleted list before deleting post
720 if (prior != NO_SNAPSHOT_ID) {
721 DirectoryDiff priorDiff = this.getDiffs().getDiffById(prior);
722 if (priorDiff != null && priorDiff.getSnapshotId() == prior) {
723 priorCreated = cloneDiffList(priorDiff.diff.getCreatedUnmodifiable());
724 priorDeleted = cloneDiffList(priorDiff.diff.getDeletedUnmodifiable());
725 }
726 }
727
728 getDiffs().deleteSnapshotDiff(reclaimContext, snapshot, prior,
729 currentINode);
730 currentINode.cleanSubtreeRecursively(reclaimContext, snapshot, prior,
731 priorDeleted);
732
733 // check priorDiff again since it may be created during the diff deletion
734 if (prior != NO_SNAPSHOT_ID) {
735 DirectoryDiff priorDiff = this.getDiffs().getDiffById(prior);
736 if (priorDiff != null && priorDiff.getSnapshotId() == prior) {
737 // For files/directories created between "prior" and "snapshot",
738 // we need to clear snapshot copies for "snapshot". Note that we must
739 // use null as prior in the cleanSubtree call. Files/directories that
740 // were created before "prior" will be covered by the later
741 // cleanSubtreeRecursively call.
742 if (priorCreated != null) {
743 // we only check the node originally in prior's created list
744 for (INode cNode : priorDiff.diff.getCreatedUnmodifiable()) {
745 if (priorCreated.containsKey(cNode)) {
746 cNode.cleanSubtree(reclaimContext, snapshot, NO_SNAPSHOT_ID);
747 }
748 }
749 }
750
751 // When a directory is moved from the deleted list of the posterior
752 // diff to the deleted list of this diff, we need to destroy its
753 // descendants that were 1) created after taking this diff and 2)
754 // deleted after taking posterior diff.
755
756 // For files moved from posterior's deleted list, we also need to
757 // delete its snapshot copy associated with the posterior snapshot.
758
759 for (INode dNode : priorDiff.diff.getDeletedUnmodifiable()) {
760 if (priorDeleted == null || !priorDeleted.containsKey(dNode)) {
761 cleanDeletedINode(reclaimContext, dNode, snapshot, prior);
762 }
763 }
764 }
765 }
766 }
767
768 QuotaCounts current = reclaimContext.quotaDelta().getCountsCopy();
769 current.subtract(old);
770 if (currentINode.isQuotaSet()) {
771 reclaimContext.quotaDelta().addQuotaDirUpdate(currentINode, current);
772 }
773 }
774 }