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