fs/btrfs/inode-item.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include "ctree.h"
  20 #include "disk-io.h"
  21 #include "hash.h"
  22 #include "transaction.h"
  23 #include "print-tree.h"
  24
  25 int btrfs_find_name_in_backref(struct extent_buffer *leaf, int slot,
  26                                const char *name,
  27                                int name_len, struct btrfs_inode_ref **ref_ret)
  28 {
  29         struct btrfs_inode_ref *ref;
  30         unsigned long ptr;
  31         unsigned long name_ptr;
  32         u32 item_size;
  33         u32 cur_offset = 0;
  34         int len;
  35
  36         item_size = btrfs_item_size_nr(leaf, slot);
  37         ptr = btrfs_item_ptr_offset(leaf, slot);
  38         while (cur_offset < item_size) {
  39                 ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
  40                 len = btrfs_inode_ref_name_len(leaf, ref);
  41                 name_ptr = (unsigned long)(ref + 1);
  42                 cur_offset += len + sizeof(*ref);
  43                 if (len != name_len)
  44                         continue;
  45                 if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) {
  46                         if (ref_ret)
  47                                 *ref_ret = ref;
  48                         return 1;
  49                 }
  50         }
  51         return 0;
  52 }
  53
  54 int btrfs_find_name_in_ext_backref(struct extent_buffer *leaf, int slot,
  55                                    u64 ref_objectid,
  56                                    const char *name, int name_len,
  57                                    struct btrfs_inode_extref **extref_ret)
  58 {
  59         struct btrfs_inode_extref *extref;
  60         unsigned long ptr;
  61         unsigned long name_ptr;
  62         u32 item_size;
  63         u32 cur_offset = 0;
  64         int ref_name_len;
  65
  66         item_size = btrfs_item_size_nr(leaf, slot);
  67         ptr = btrfs_item_ptr_offset(leaf, slot);
  68
  69         /*
  70          * Search all extended backrefs in this item. We're only
  71          * looking through any collisions so most of the time this is
  72          * just going to compare against one buffer. If all is well,
  73          * we'll return success and the inode ref object.
  74          */
  75         while (cur_offset < item_size) {
  76                 extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
  77                 name_ptr = (unsigned long)(&extref->name);
  78                 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
  79
  80                 if (ref_name_len == name_len &&
  81                     btrfs_inode_extref_parent(leaf, extref) == ref_objectid &&
  82                     (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) {
  83                         if (extref_ret)
  84                                 *extref_ret = extref;
  85                         return 1;
  86                 }
  87
  88                 cur_offset += ref_name_len + sizeof(*extref);
  89         }
  90         return 0;
  91 }
  92
  93 /* Returns NULL if no extref found */
  94 struct btrfs_inode_extref *
  95 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans,
  96                           struct btrfs_root *root,
  97                           struct btrfs_path *path,
  98                           const char *name, int name_len,
  99                           u64 inode_objectid, u64 ref_objectid, int ins_len,
 100                           int cow)
 101 {
 102         int ret;
 103         struct btrfs_key key;
 104         struct btrfs_inode_extref *extref;
 105
 106         key.objectid = inode_objectid;
 107         key.type = BTRFS_INODE_EXTREF_KEY;
 108         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 109
 110         ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
 111         if (ret < 0)
 112                 return ERR_PTR(ret);
 113         if (ret > 0)
 114                 return NULL;
 115         if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
 116                                             ref_objectid, name, name_len,
 117                                             &extref))
 118                 return NULL;
 119         return extref;
 120 }
 121
 122 static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
 123                                   struct btrfs_root *root,
 124                                   const char *name, int name_len,
 125                                   u64 inode_objectid, u64 ref_objectid,
 126                                   u64 *index)
 127 {
 128         struct btrfs_path *path;
 129         struct btrfs_key key;
 130         struct btrfs_inode_extref *extref;
 131         struct extent_buffer *leaf;
 132         int ret;
 133         int del_len = name_len + sizeof(*extref);
 134         unsigned long ptr;
 135         unsigned long item_start;
 136         u32 item_size;
 137
 138         key.objectid = inode_objectid;
 139         key.type = BTRFS_INODE_EXTREF_KEY;
 140         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 141
 142         path = btrfs_alloc_path();
 143         if (!path)
 144                 return -ENOMEM;
 145
 146         path->leave_spinning = 1;
 147
 148         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 149         if (ret > 0)
 150                 ret = -ENOENT;
 151         if (ret < 0)
 152                 goto out;
 153
 154         /*
 155          * Sanity check - did we find the right item for this name?
 156          * This should always succeed so error here will make the FS
 157          * readonly.
 158          */
 159         if (!btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0],
 160                                             ref_objectid,
 161                                             name, name_len, &extref)) {
 162                 btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL);
 163                 ret = -EROFS;
 164                 goto out;
 165         }
 166
 167         leaf = path->nodes[0];
 168         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 169         if (index)
 170                 *index = btrfs_inode_extref_index(leaf, extref);
 171
 172         if (del_len == item_size) {
 173                 /*
 174                  * Common case only one ref in the item, remove the
 175                  * whole item.
 176                  */
 177                 ret = btrfs_del_item(trans, root, path);
 178                 goto out;
 179         }
 180
 181         ptr = (unsigned long)extref;
 182         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 183
 184         memmove_extent_buffer(leaf, ptr, ptr + del_len,
 185                               item_size - (ptr + del_len - item_start));
 186
 187         btrfs_truncate_item(root->fs_info, path, item_size - del_len, 1);
 188
 189 out:
 190         btrfs_free_path(path);
 191
 192         return ret;
 193 }
 194
 195 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
 196                         struct btrfs_root *root,
 197                         const char *name, int name_len,
 198                         u64 inode_objectid, u64 ref_objectid, u64 *index)
 199 {
 200         struct btrfs_path *path;
 201         struct btrfs_key key;
 202         struct btrfs_inode_ref *ref;
 203         struct extent_buffer *leaf;
 204         unsigned long ptr;
 205         unsigned long item_start;
 206         u32 item_size;
 207         u32 sub_item_len;
 208         int ret;
 209         int search_ext_refs = 0;
 210         int del_len = name_len + sizeof(*ref);
 211
 212         key.objectid = inode_objectid;
 213         key.offset = ref_objectid;
 214         key.type = BTRFS_INODE_REF_KEY;
 215
 216         path = btrfs_alloc_path();
 217         if (!path)
 218                 return -ENOMEM;
 219
 220         path->leave_spinning = 1;
 221
 222         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 223         if (ret > 0) {
 224                 ret = -ENOENT;
 225                 search_ext_refs = 1;
 226                 goto out;
 227         } else if (ret < 0) {
 228                 goto out;
 229         }
 230         if (!btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
 231                                         name, name_len, &ref)) {
 232                 ret = -ENOENT;
 233                 search_ext_refs = 1;
 234                 goto out;
 235         }
 236         leaf = path->nodes[0];
 237         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 238
 239         if (index)
 240                 *index = btrfs_inode_ref_index(leaf, ref);
 241
 242         if (del_len == item_size) {
 243                 ret = btrfs_del_item(trans, root, path);
 244                 goto out;
 245         }
 246         ptr = (unsigned long)ref;
 247         sub_item_len = name_len + sizeof(*ref);
 248         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 249         memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
 250                               item_size - (ptr + sub_item_len - item_start));
 251         btrfs_truncate_item(root->fs_info, path, item_size - sub_item_len, 1);
 252 out:
 253         btrfs_free_path(path);
 254
 255         if (search_ext_refs) {
 256                 /*
 257                  * No refs were found, or we could not find the
 258                  * name in our ref array. Find and remove the extended
 259                  * inode ref then.
 260                  */
 261                 return btrfs_del_inode_extref(trans, root, name, name_len,
 262                                               inode_objectid, ref_objectid, index);
 263         }
 264
 265         return ret;
 266 }
 267
 268 /*
 269  * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
 270  *
 271  * The caller must have checked against BTRFS_LINK_MAX already.
 272  */
 273 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
 274                                      struct btrfs_root *root,
 275                                      const char *name, int name_len,
 276                                      u64 inode_objectid, u64 ref_objectid, u64 index)
 277 {
 278         struct btrfs_inode_extref *extref;
 279         int ret;
 280         int ins_len = name_len + sizeof(*extref);
 281         unsigned long ptr;
 282         struct btrfs_path *path;
 283         struct btrfs_key key;
 284         struct extent_buffer *leaf;
 285         struct btrfs_item *item;
 286
 287         key.objectid = inode_objectid;
 288         key.type = BTRFS_INODE_EXTREF_KEY;
 289         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 290
 291         path = btrfs_alloc_path();
 292         if (!path)
 293                 return -ENOMEM;
 294
 295         path->leave_spinning = 1;
 296         ret = btrfs_insert_empty_item(trans, root, path, &key,
 297                                       ins_len);
 298         if (ret == -EEXIST) {
 299                 if (btrfs_find_name_in_ext_backref(path->nodes[0],
 300                                                    path->slots[0],
 301                                                    ref_objectid,
 302                                                    name, name_len, NULL))
 303                         goto out;
 304
 305                 btrfs_extend_item(root->fs_info, path, ins_len);
 306                 ret = 0;
 307         }
 308         if (ret < 0)
 309                 goto out;
 310
 311         leaf = path->nodes[0];
 312         item = btrfs_item_nr(path->slots[0]);
 313         ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
 314         ptr += btrfs_item_size(leaf, item) - ins_len;
 315         extref = (struct btrfs_inode_extref *)ptr;
 316
 317         btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
 318         btrfs_set_inode_extref_index(path->nodes[0], extref, index);
 319         btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
 320
 321         ptr = (unsigned long)&extref->name;
 322         write_extent_buffer(path->nodes[0], name, ptr, name_len);
 323         btrfs_mark_buffer_dirty(path->nodes[0]);
 324
 325 out:
 326         btrfs_free_path(path);
 327         return ret;
 328 }
 329
 330 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
 331 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
 332                            struct btrfs_root *root,
 333                            const char *name, int name_len,
 334                            u64 inode_objectid, u64 ref_objectid, u64 index)
 335 {
 336         struct btrfs_fs_info *fs_info = root->fs_info;
 337         struct btrfs_path *path;
 338         struct btrfs_key key;
 339         struct btrfs_inode_ref *ref;
 340         unsigned long ptr;
 341         int ret;
 342         int ins_len = name_len + sizeof(*ref);
 343
 344         key.objectid = inode_objectid;
 345         key.offset = ref_objectid;
 346         key.type = BTRFS_INODE_REF_KEY;
 347
 348         path = btrfs_alloc_path();
 349         if (!path)
 350                 return -ENOMEM;
 351
 352         path->leave_spinning = 1;
 353         path->skip_release_on_error = 1;
 354         ret = btrfs_insert_empty_item(trans, root, path, &key,
 355                                       ins_len);
 356         if (ret == -EEXIST) {
 357                 u32 old_size;
 358
 359                 if (btrfs_find_name_in_backref(path->nodes[0], path->slots[0],
 360                                                name, name_len, &ref))
 361                         goto out;
 362
 363                 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
 364                 btrfs_extend_item(fs_info, path, ins_len);
 365                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 366                                      struct btrfs_inode_ref);
 367                 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
 368                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
 369                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
 370                 ptr = (unsigned long)(ref + 1);
 371                 ret = 0;
 372         } else if (ret < 0) {
 373                 if (ret == -EOVERFLOW) {
 374                         if (btrfs_find_name_in_backref(path->nodes[0],
 375                                                        path->slots[0],
 376                                                        name, name_len, &ref))
 377                                 ret = -EEXIST;
 378                         else
 379                                 ret = -EMLINK;
 380                 }
 381                 goto out;
 382         } else {
 383                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 384                                      struct btrfs_inode_ref);
 385                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
 386                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
 387                 ptr = (unsigned long)(ref + 1);
 388         }
 389         write_extent_buffer(path->nodes[0], name, ptr, name_len);
 390         btrfs_mark_buffer_dirty(path->nodes[0]);
 391
 392 out:
 393         btrfs_free_path(path);
 394
 395         if (ret == -EMLINK) {
 396                 struct btrfs_super_block *disk_super = fs_info->super_copy;
 397                 /* We ran out of space in the ref array. Need to
 398                  * add an extended ref. */
 399                 if (btrfs_super_incompat_flags(disk_super)
 400                     & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
 401                         ret = btrfs_insert_inode_extref(trans, root, name,
 402                                                         name_len,
 403                                                         inode_objectid,
 404                                                         ref_objectid, index);
 405         }
 406
 407         return ret;
 408 }
 409
 410 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
 411                              struct btrfs_root *root,
 412                              struct btrfs_path *path, u64 objectid)
 413 {
 414         struct btrfs_key key;
 415         int ret;
 416         key.objectid = objectid;
 417         key.type = BTRFS_INODE_ITEM_KEY;
 418         key.offset = 0;
 419
 420         ret = btrfs_insert_empty_item(trans, root, path, &key,
 421                                       sizeof(struct btrfs_inode_item));
 422         return ret;
 423 }
 424
 425 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 426                        *root, struct btrfs_path *path,
 427                        struct btrfs_key *location, int mod)
 428 {
 429         int ins_len = mod < 0 ? -1 : 0;
 430         int cow = mod != 0;
 431         int ret;
 432         int slot;
 433         struct extent_buffer *leaf;
 434         struct btrfs_key found_key;
 435
 436         ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
 437         if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY &&
 438             location->offset == (u64)-1 && path->slots[0] != 0) {
 439                 slot = path->slots[0] - 1;
 440                 leaf = path->nodes[0];
 441                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
 442                 if (found_key.objectid == location->objectid &&
 443                     found_key.type == location->type) {
 444                         path->slots[0]--;
 445                         return 0;
 446                 }
 447         }
 448         return ret;
 449 }