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