/** * Copyright 2005 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * *     http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */package org.apache.hadoop.dfs;import org.apache.hadoop.io.*;import java.io.*;import java.util.*;import org.apache.hadoop.conf.Configuration;import org.apache.hadoop.fs.FileUtil;/************************************************* * FSDirectory stores the filesystem directory state. * It handles writing/loading values to disk, and logging * changes as we go. * * It keeps the filename->blockset mapping always-current * and logged to disk. *  * @author Mike Cafarella *************************************************/class FSDirectory implements FSConstants {    static String FS_IMAGE = "fsimage";    static String NEW_FS_IMAGE = "fsimage.new";    static String OLD_FS_IMAGE = "fsimage.old";    private static final byte OP_ADD = 0;    private static final byte OP_RENAME = 1;    private static final byte OP_DELETE = 2;    private static final byte OP_MKDIR = 3;    /******************************************************     * We keep an in-memory representation of the file/block     * hierarchy.     ******************************************************/    class INode {        public String name;        public INode parent;        public TreeMap children = new TreeMap();        public Block blocks[];        /**         */        INode(String name, INode parent, Block blocks[]) {            this.name = name;            this.parent = parent;            this.blocks = blocks;        }        /**         * Check whether it's a directory         * @return         */        synchronized public boolean isDir() {          return (blocks == null);        }        /**         * This is the external interface         */        INode getNode(String target) {            if (! target.startsWith("/") || target.length() == 0) {                return null;            } else if (parent == null && "/".equals(target)) {                return this;            } else {                Vector components = new Vector();                int start = 0;                int slashid = 0;                while (start < target.length() && (slashid = target.indexOf('/', start)) >= 0) {                    components.add(target.substring(start, slashid));                    start = slashid + 1;                }                if (start < target.length()) {                    components.add(target.substring(start));                }                return getNode(components, 0);            }        }        /**         */        INode getNode(Vector components, int index) {            if (! name.equals((String) components.elementAt(index))) {                return null;            }            if (index == components.size()-1) {                return this;            }            // Check with children            INode child = (INode) children.get(components.elementAt(index+1));            if (child == null) {                return null;            } else {                return child.getNode(components, index+1);            }        }        /**         */        INode addNode(String target, Block blks[]) {            if (getNode(target) != null) {                return null;            } else {                String parentName = DFSFile.getDFSParent(target);                if (parentName == null) {                    return null;                }                INode parentNode = getNode(parentName);                if (parentNode == null) {                    return null;                } else {                    String targetName = new File(target).getName();                    INode newItem = new INode(targetName, parentNode, blks);                    parentNode.children.put(targetName, newItem);                    return newItem;                }            }        }        /**         */        boolean removeNode() {            if (parent == null) {                return false;            } else {                parent.children.remove(name);                return true;            }        }        /**         * Collect all the blocks at this INode and all its children.         * This operation is performed after a node is removed from the tree,         * and we want to GC all the blocks at this node and below.         */        void collectSubtreeBlocks(Vector v) {            if (blocks != null) {                for (int i = 0; i < blocks.length; i++) {                    v.add(blocks[i]);                }            }            for (Iterator it = children.values().iterator(); it.hasNext(); ) {                INode child = (INode) it.next();                child.collectSubtreeBlocks(v);            }        }        /**         */        int numItemsInTree() {            int total = 0;            for (Iterator it = children.values().iterator(); it.hasNext(); ) {                INode child = (INode) it.next();                total += child.numItemsInTree();            }            return total + 1;        }        /**         */        String computeName() {            if (parent != null) {                return parent.computeName() + "/" + name;            } else {                return name;            }        }        /**         */        long computeFileLength() {            long total = 0;            if (blocks != null) {                for (int i = 0; i < blocks.length; i++) {                    total += blocks[i].getNumBytes();                }            }            return total;        }        /**         */        long computeContentsLength() {            long total = computeFileLength();            for (Iterator it = children.values().iterator(); it.hasNext(); ) {                INode child = (INode) it.next();                total += child.computeContentsLength();            }            return total;        }        /**         */        void listContents(Vector v) {            if (parent != null && blocks != null) {                v.add(this);            }            for (Iterator it = children.values().iterator(); it.hasNext(); ) {                INode child = (INode) it.next();                v.add(child);            }        }        /**         */        void saveImage(String parentPrefix, DataOutputStream out) throws IOException {            String fullName = "";            if (parent != null) {                fullName = parentPrefix + "/" + name;                new UTF8(fullName).write(out);                if (blocks == null) {                    out.writeInt(0);                } else {                    out.writeInt(blocks.length);                    for (int i = 0; i < blocks.length; i++) {                        blocks[i].write(out);                    }                }            }            for (Iterator it = children.values().iterator(); it.hasNext(); ) {                INode child = (INode) it.next();                child.saveImage(fullName, out);            }        }    }    INode rootDir = new INode("", null, null);    TreeSet activeBlocks = new TreeSet();    TreeMap activeLocks = new TreeMap();    DataOutputStream editlog = null;    boolean ready = false;    /** Access an existing dfs name directory. */    public FSDirectory(File dir) throws IOException {        File fullimage = new File(dir, "image");        if (! fullimage.exists()) {          throw new IOException("NameNode not formatted: " + dir);        }        File edits = new File(dir, "edits");        if (loadFSImage(fullimage, edits)) {            saveFSImage(fullimage, edits);        }        synchronized (this) {            this.ready = true;            this.notifyAll();            this.editlog = new DataOutputStream(new FileOutputStream(edits));        }    }    /** Create a new dfs name directory.  Caution: this destroys all files     * in this filesystem. */    public static void format(File dir, Configuration conf)      throws IOException {        File image = new File(dir, "image");        File edits = new File(dir, "edits");        if (!((!image.exists() || FileUtil.fullyDelete(image, conf)) &&              (!edits.exists() || edits.delete()) &&              image.mkdirs())) {                    throw new IOException("Unable to format: "+dir);        }    }    /**     * Shutdown the filestore     */    public void close() throws IOException {        editlog.close();    }    /**     * Block until the object is ready to be used.     */    void waitForReady() {        if (! ready) {            synchronized (this) {                while (!ready) {                    try {                        this.wait(5000);                    } catch (InterruptedException ie) {                    }                }            }        }    }    /**     * Load in the filesystem image.  It's a big list of     * filenames and blocks.  Return whether we should     * "re-save" and consolidate the edit-logs     */    boolean loadFSImage(File fsdir, File edits) throws IOException {        //        // Atomic move sequence, to recover from interrupted save        //        File curFile = new File(fsdir, FS_IMAGE);        File newFile = new File(fsdir, NEW_FS_IMAGE);        File oldFile = new File(fsdir, OLD_FS_IMAGE);        // Maybe we were interrupted between 2 and 4        if (oldFile.exists() && curFile.exists()) {            oldFile.delete();            if (edits.exists()) {                edits.delete();            }        } else if (oldFile.exists() && newFile.exists()) {            // Or maybe between 1 and 2            newFile.renameTo(curFile);            oldFile.delete();        } else if (curFile.exists() && newFile.exists()) {            // Or else before stage 1, in which case we lose the edits            newFile.delete();        }        //        // Load in bits        //        if (curFile.exists()) {            DataInputStream in = new DataInputStream(new BufferedInputStream(new FileInputStream(curFile)));            try {                int numFiles = in.readInt();                for (int i = 0; i < numFiles; i++) {                    UTF8 name = new UTF8();                    name.readFields(in);                    int numBlocks = in.readInt();                    if (numBlocks == 0) {                        unprotectedAddFile(name, null);                    } else {                        Block blocks[] = new Block[numBlocks];                        for (int j = 0; j < numBlocks; j++) {                            blocks[j] = new Block();                            blocks[j].readFields(in);                        }                        unprotectedAddFile(name, blocks);                    }                }            } finally {                in.close();            }        }        if (edits.exists() && loadFSEdits(edits) > 0) {            return true;        } else {            return false;        }    }    /**     * Load an edit log, and apply the changes to the in-memory structure     *     * This is where we apply edits that we've been writing to disk all     * along.     */    int loadFSEdits(File edits) throws IOException {        int numEdits = 0;        if (edits.exists()) {            DataInputStream in = new DataInputStream(new BufferedInputStream(new FileInputStream(edits)));            try {