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 static 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,
 190                                   u64 *index)
 191 {
 192         struct btrfs_path *path;
 193         struct btrfs_key key;
 194         struct btrfs_inode_extref *extref;
 195         struct extent_buffer *leaf;
 196         int ret;
 197         int del_len = name_len + sizeof(*extref);
 198         unsigned long ptr;
 199         unsigned long item_start;
 200         u32 item_size;
 201
 202         key.objectid = inode_objectid;
 203         btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY);
 204         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 205
 206         path = btrfs_alloc_path();
 207         if (!path)
 208                 return -ENOMEM;
 209
 210         path->leave_spinning = 1;
 211
 212         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 213         if (ret > 0)
 214                 ret = -ENOENT;
 215         if (ret < 0)
 216                 goto out;
 217
 218         /*
 219          * Sanity check - did we find the right item for this name?
 220          * This should always succeed so error here will make the FS
 221          * readonly.
 222          */
 223         if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
 224                                             name, name_len, &extref)) {
 225                 btrfs_std_error(root->fs_info, -ENOENT);
 226                 ret = -EROFS;
 227                 goto out;
 228         }
 229
 230         leaf = path->nodes[0];
 231         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 232         if (index)
 233                 *index = btrfs_inode_extref_index(leaf, extref);
 234
 235         if (del_len == item_size) {
 236                 /*
 237                  * Common case only one ref in the item, remove the
 238                  * whole item.
 239                  */
 240                 ret = btrfs_del_item(trans, root, path);
 241                 goto out;
 242         }
 243
 244         ptr = (unsigned long)extref;
 245         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 246
 247         memmove_extent_buffer(leaf, ptr, ptr + del_len,
 248                               item_size - (ptr + del_len - item_start));
 249
 250         btrfs_truncate_item(root, path, item_size - del_len, 1);
 251
 252 out:
 253         btrfs_free_path(path);
 254
 255         return ret;
 256 }
 257
 258 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
 259                         struct btrfs_root *root,
 260                         const char *name, int name_len,
 261                         u64 inode_objectid, u64 ref_objectid, u64 *index)
 262 {
 263         struct btrfs_path *path;
 264         struct btrfs_key key;
 265         struct btrfs_inode_ref *ref;
 266         struct extent_buffer *leaf;
 267         unsigned long ptr;
 268         unsigned long item_start;
 269         u32 item_size;
 270         u32 sub_item_len;
 271         int ret;
 272         int search_ext_refs = 0;
 273         int del_len = name_len + sizeof(*ref);
 274
 275         key.objectid = inode_objectid;
 276         key.offset = ref_objectid;
 277         btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
 278
 279         path = btrfs_alloc_path();
 280         if (!path)
 281                 return -ENOMEM;
 282
 283         path->leave_spinning = 1;
 284
 285         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 286         if (ret > 0) {
 287                 ret = -ENOENT;
 288                 search_ext_refs = 1;
 289                 goto out;
 290         } else if (ret < 0) {
 291                 goto out;
 292         }
 293         if (!find_name_in_backref(path, name, name_len, &ref)) {
 294                 ret = -ENOENT;
 295                 search_ext_refs = 1;
 296                 goto out;
 297         }
 298         leaf = path->nodes[0];
 299         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 300
 301         if (index)
 302                 *index = btrfs_inode_ref_index(leaf, ref);
 303
 304         if (del_len == item_size) {
 305                 ret = btrfs_del_item(trans, root, path);
 306                 goto out;
 307         }
 308         ptr = (unsigned long)ref;
 309         sub_item_len = name_len + sizeof(*ref);
 310         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 311         memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
 312                               item_size - (ptr + sub_item_len - item_start));
 313         btrfs_truncate_item(root, path, item_size - sub_item_len, 1);
 314 out:
 315         btrfs_free_path(path);
 316
 317         if (search_ext_refs) {
 318                 /*
 319                  * No refs were found, or we could not find the
 320                  * name in our ref array. Find and remove the extended
 321                  * inode ref then.
 322                  */
 323                 return btrfs_del_inode_extref(trans, root, name, name_len,
 324                                               inode_objectid, ref_objectid, index);
 325         }
 326
 327         return ret;
 328 }
 329
 330 /*
 331  * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree.
 332  *
 333  * The caller must have checked against BTRFS_LINK_MAX already.
 334  */
 335 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans,
 336                                      struct btrfs_root *root,
 337                                      const char *name, int name_len,
 338                                      u64 inode_objectid, u64 ref_objectid, u64 index)
 339 {
 340         struct btrfs_inode_extref *extref;
 341         int ret;
 342         int ins_len = name_len + sizeof(*extref);
 343         unsigned long ptr;
 344         struct btrfs_path *path;
 345         struct btrfs_key key;
 346         struct extent_buffer *leaf;
 347         struct btrfs_item *item;
 348
 349         key.objectid = inode_objectid;
 350         key.type = BTRFS_INODE_EXTREF_KEY;
 351         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 352
 353         path = btrfs_alloc_path();
 354         if (!path)
 355                 return -ENOMEM;
 356
 357         path->leave_spinning = 1;
 358         ret = btrfs_insert_empty_item(trans, root, path, &key,
 359                                       ins_len);
 360         if (ret == -EEXIST) {
 361                 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
 362                                                    name, name_len, NULL))
 363                         goto out;
 364
 365                 btrfs_extend_item(root, path, ins_len);
 366                 ret = 0;
 367         }
 368         if (ret < 0)
 369                 goto out;
 370
 371         leaf = path->nodes[0];
 372         item = btrfs_item_nr(leaf, path->slots[0]);
 373         ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char);
 374         ptr += btrfs_item_size(leaf, item) - ins_len;
 375         extref = (struct btrfs_inode_extref *)ptr;
 376
 377         btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len);
 378         btrfs_set_inode_extref_index(path->nodes[0], extref, index);
 379         btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid);
 380
 381         ptr = (unsigned long)&extref->name;
 382         write_extent_buffer(path->nodes[0], name, ptr, name_len);
 383         btrfs_mark_buffer_dirty(path->nodes[0]);
 384
 385 out:
 386         btrfs_free_path(path);
 387         return ret;
 388 }
 389
 390 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */
 391 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
 392                            struct btrfs_root *root,
 393                            const char *name, int name_len,
 394                            u64 inode_objectid, u64 ref_objectid, u64 index)
 395 {
 396         struct btrfs_path *path;
 397         struct btrfs_key key;
 398         struct btrfs_inode_ref *ref;
 399         unsigned long ptr;
 400         int ret;
 401         int ins_len = name_len + sizeof(*ref);
 402
 403         key.objectid = inode_objectid;
 404         key.offset = ref_objectid;
 405         btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
 406
 407         path = btrfs_alloc_path();
 408         if (!path)
 409                 return -ENOMEM;
 410
 411         path->leave_spinning = 1;
 412         ret = btrfs_insert_empty_item(trans, root, path, &key,
 413                                       ins_len);
 414         if (ret == -EEXIST) {
 415                 u32 old_size;
 416
 417                 if (find_name_in_backref(path, name, name_len, &ref))
 418                         goto out;
 419
 420                 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
 421                 btrfs_extend_item(root, path, ins_len);
 422                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 423                                      struct btrfs_inode_ref);
 424                 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
 425                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
 426                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
 427                 ptr = (unsigned long)(ref + 1);
 428                 ret = 0;
 429         } else if (ret < 0) {
 430                 if (ret == -EOVERFLOW)
 431                         ret = -EMLINK;
 432                 goto out;
 433         } else {
 434                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 435                                      struct btrfs_inode_ref);
 436                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
 437                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
 438                 ptr = (unsigned long)(ref + 1);
 439         }
 440         write_extent_buffer(path->nodes[0], name, ptr, name_len);
 441         btrfs_mark_buffer_dirty(path->nodes[0]);
 442
 443 out:
 444         btrfs_free_path(path);
 445
 446         if (ret == -EMLINK) {
 447                 struct btrfs_super_block *disk_super = root->fs_info->super_copy;
 448                 /* We ran out of space in the ref array. Need to
 449                  * add an extended ref. */
 450                 if (btrfs_super_incompat_flags(disk_super)
 451                     & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)
 452                         ret = btrfs_insert_inode_extref(trans, root, name,
 453                                                         name_len,
 454                                                         inode_objectid,
 455                                                         ref_objectid, index);
 456         }
 457
 458         return ret;
 459 }
 460
 461 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans,
 462                              struct btrfs_root *root,
 463                              struct btrfs_path *path, u64 objectid)
 464 {
 465         struct btrfs_key key;
 466         int ret;
 467         key.objectid = objectid;
 468         btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY);
 469         key.offset = 0;
 470
 471         ret = btrfs_insert_empty_item(trans, root, path, &key,
 472                                       sizeof(struct btrfs_inode_item));
 473         return ret;
 474 }
 475
 476 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 477                        *root, struct btrfs_path *path,
 478                        struct btrfs_key *location, int mod)
 479 {
 480         int ins_len = mod < 0 ? -1 : 0;
 481         int cow = mod != 0;
 482         int ret;
 483         int slot;
 484         struct extent_buffer *leaf;
 485         struct btrfs_key found_key;
 486
 487         ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
 488         if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY &&
 489             location->offset == (u64)-1 && path->slots[0] != 0) {
 490                 slot = path->slots[0] - 1;
 491                 leaf = path->nodes[0];
 492                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
 493                 if (found_key.objectid == location->objectid &&
 494                     btrfs_key_type(&found_key) == btrfs_key_type(location)) {
 495                         path->slots[0]--;
 496                         return 0;
 497                 }
 498         }
 499         return ret;
 500 }