3 files changed, 107 insertions, 11 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 61d7b4738af6..794f7e4f1c07 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -270,6 +270,10 @@ struct btrfs_root {
 #define BTRFS_KEY_TYPE_MAX      256
 #define BTRFS_KEY_TYPE_MASK     (BTRFS_KEY_TYPE_MAX - 1)
 
+#define BTRFS_KEY_OVERFLOW_MAX 128
+#define BTRFS_KEY_OVERFLOW_SHIFT 8
+#define BTRFS_KEY_OVERFLOW_MASK (0x7FULL << BTRFS_KEY_OVERFLOW_SHIFT)
+
 /*
  * inode items have the data typically returned from stat and store other
  * info about object characteristics.  There is one for every file and dir in
@@ -588,6 +592,19 @@ static inline void btrfs_set_disk_key_flags(struct btrfs_disk_key *disk,
         disk->flags = cpu_to_le32(val);
 }
 
+static inline u32 btrfs_key_overflow(struct btrfs_key *key)
+{
+        u32 over = key->flags & BTRFS_KEY_OVERFLOW_MASK;
+        return over >> BTRFS_KEY_OVERFLOW_SHIFT;
+}
+
+static inline void btrfs_set_key_overflow(struct btrfs_key *key, u32 over)
+{
+        BUG_ON(over > BTRFS_KEY_OVERFLOW_MAX);
+        over = over << BTRFS_KEY_OVERFLOW_SHIFT;
+        key->flags = (key->flags & ~((u64)BTRFS_KEY_OVERFLOW_MASK)) | over;
+}
+
 static inline u32 btrfs_key_type(struct btrfs_key *key)
 {
         return key->flags & BTRFS_KEY_TYPE_MASK;
@@ -612,6 +629,22 @@ static inline void btrfs_set_disk_key_type(struct btrfs_disk_key *key, u32 type)
         btrfs_set_disk_key_flags(key, flags);
 }
 
+static inline u32 btrfs_disk_key_overflow(struct btrfs_disk_key *key)
+{
+        u32 over = le32_to_cpu(key->flags) & BTRFS_KEY_OVERFLOW_MASK;
+        return over >> BTRFS_KEY_OVERFLOW_SHIFT;
+}
+
+static inline void btrfs_set_disK_key_overflow(struct btrfs_disk_key *key,
+                                               u32 over)
+{
+        u32 flags = btrfs_disk_key_flags(key);
+        BUG_ON(over > BTRFS_KEY_OVERFLOW_MAX);
+        over = over << BTRFS_KEY_OVERFLOW_SHIFT;
+        flags = (flags & ~((u64)BTRFS_KEY_OVERFLOW_MASK)) | over;
+        btrfs_set_disk_key_flags(key, flags);
+}
+
 static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
 {
         return le64_to_cpu(h->blocknr);
diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
index 62d0c0916a73..b1629a5d73c8 100644
--- a/fs/btrfs/dir-item.c
+++ b/fs/btrfs/dir-item.c
@@ -4,6 +4,26 @@
 #include "hash.h"
 #include "transaction.h"
 
+int insert_with_overflow(struct btrfs_trans_handle *trans, struct btrfs_root
+                            *root, struct btrfs_path *path, struct btrfs_key
+                            *cpu_key, u32 data_size)
+{
+        int overflow;
+        int ret;
+
+        ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
+        overflow = btrfs_key_overflow(cpu_key);
+
+        while(ret == -EEXIST && overflow < BTRFS_KEY_OVERFLOW_MAX) {
+                overflow++;
+                btrfs_set_key_overflow(cpu_key, overflow);
+                btrfs_release_path(root, path);
+                ret = btrfs_insert_empty_item(trans, root, path, cpu_key,
+                                              data_size);
+        }
+        return ret;
+}
+
 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
                           *root, const char *name, int name_len, u64 dir, u64
                           objectid, u8 type)
@@ -23,7 +43,7 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
         path = btrfs_alloc_path();
         btrfs_init_path(path);
         data_size = sizeof(*dir_item) + name_len;
-        ret = btrfs_insert_empty_item(trans, root, path, &key, data_size);
+        ret = insert_with_overflow(trans, root, path, &key, data_size);
         if (ret)
                 goto out;
 
@@ -41,7 +61,7 @@ int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
 
         btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY);
         key.offset = objectid;
-        ret = btrfs_insert_empty_item(trans, root, path, &key, data_size);
+        ret = insert_with_overflow(trans, root, path, &key, data_size);
         // FIXME clear the dirindex bit
         if (ret)
                 goto out;
@@ -70,14 +90,40 @@ int btrfs_lookup_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root
         struct btrfs_key key;
         int ins_len = mod < 0 ? -1 : 0;
         int cow = mod != 0;
+        struct btrfs_disk_key *found_key;
+        struct btrfs_leaf *leaf;
 
         key.objectid = dir;
         key.flags = 0;
         btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY);
+        btrfs_set_key_overflow(&key, BTRFS_KEY_OVERFLOW_MAX - 1);
         ret = btrfs_name_hash(name, name_len, &key.offset);
         BUG_ON(ret);
-        ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
-        return ret;
+        while(1) {
+                ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
+                if (ret < 0)
+                        return ret;
+                if (ret > 0) {
+                        if (path->slots[0] == 0)
+                                return 1;
+                        path->slots[0]--;
+                }
+                leaf = btrfs_buffer_leaf(path->nodes[0]);
+                found_key = &leaf->items[path->slots[0]].key;
+
+                if (btrfs_disk_key_objectid(found_key) != dir ||
+                    btrfs_disk_key_type(found_key) != BTRFS_DIR_ITEM_KEY ||
+                    btrfs_disk_key_offset(found_key) != key.offset)
+                        return 1;
+
+                if (btrfs_match_dir_item_name(root, path, name, name_len))
+                        return 0;
+
+                if (btrfs_disk_key_overflow(found_key) == 0)
+                        return 1;
+                btrfs_release_path(root, path);
+        }
+        return 1;
 }
 
 int btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans,
@@ -89,13 +135,31 @@ int btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans,
         struct btrfs_key key;
         int ins_len = mod < 0 ? -1 : 0;
         int cow = mod != 0;
+        struct btrfs_disk_key *found_key;
+        struct btrfs_leaf *leaf;
 
         key.objectid = dir;
         key.flags = 0;
         btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY);
+        btrfs_set_key_overflow(&key, BTRFS_KEY_OVERFLOW_MAX - 1);
         key.offset = objectid;
         ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
-        return ret;
+        if (ret < 0)
+                return ret;
+        if (ret > 0) {
+                if (path->slots[0] == 0)
+                        return 1;
+                path->slots[0]--;
+        }
+        leaf = btrfs_buffer_leaf(path->nodes[0]);
+        found_key = &leaf->items[path->slots[0]].key;
+
+        if (btrfs_disk_key_objectid(found_key) != dir ||
+            btrfs_disk_key_type(found_key) != BTRFS_DIR_INDEX_KEY)
+                return 1;
+        if (btrfs_disk_key_offset(found_key) == objectid)
+                return 0;
+        return 1;
 }
 
 int btrfs_match_dir_item_name(struct btrfs_root *root,
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index d776b29a1676..4fd2b168b2c4 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -486,19 +486,18 @@ static int btrfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
                         continue;
                 if (btrfs_disk_key_offset(&item->key) < filp->f_pos)
                         continue;
-
+                filp->f_pos = btrfs_disk_key_offset(&item->key);
                 advance = 1;
                 di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
                 over = filldir(dirent, (const char *)(di + 1),
                                btrfs_dir_name_len(di),
                                btrfs_disk_key_offset(&item->key),
                                btrfs_dir_objectid(di), d_type);
-                if (over) {
-                        filp->f_pos = btrfs_disk_key_offset(&item->key);
-                        break;
-                }
-                filp->f_pos = btrfs_disk_key_offset(&item->key) + 1;
+                if (over)
+                        goto nopos;
         }
+        filp->f_pos++;
+nopos:
         ret = 0;
 err:
         btrfs_release_path(root, path);