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 "crc32c.h"
  23
  24 static int find_name_in_backref(struct btrfs_path *path, const char * name,
  25                          int name_len, struct btrfs_inode_ref **ref_ret)
  26 {
  27         struct extent_buffer *leaf;
  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         leaf = path->nodes[0];
  36         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  37         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
  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                         *ref_ret = ref;
  47                         return 1;
  48                 }
  49         }
  50         return 0;
  51 }
  52
  53 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans,
  54                            struct btrfs_root *root,
  55                            const char *name, int name_len,
  56                            u64 inode_objectid, u64 ref_objectid, u64 index)
  57 {
  58         struct btrfs_path *path;
  59         struct btrfs_key key;
  60         struct btrfs_inode_ref *ref;
  61         unsigned long ptr;
  62         int ret;
  63         int ins_len = name_len + sizeof(*ref);
  64
  65         key.objectid = inode_objectid;
  66         key.offset = ref_objectid;
  67         btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY);
  68
  69         path = btrfs_alloc_path();
  70         if (!path)
  71                 return -ENOMEM;
  72
  73         ret = btrfs_insert_empty_item(trans, root, path, &key,
  74                                       ins_len);
  75         if (ret == -EEXIST) {
  76                 u32 old_size;
  77
  78                 if (find_name_in_backref(path, name, name_len, &ref))
  79                         goto out;
  80
  81                 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
  82                 ret = btrfs_extend_item(trans, root, path, ins_len);
  83                 BUG_ON(ret);
  84                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  85                                      struct btrfs_inode_ref);
  86                 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size);
  87                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
  88                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
  89                 ptr = (unsigned long)(ref + 1);
  90                 ret = 0;
  91         } else if (ret < 0) {
  92                 if (ret == -EOVERFLOW)
  93                         ret = -EMLINK;
  94                 goto out;
  95         } else {
  96                 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  97                                      struct btrfs_inode_ref);
  98                 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len);
  99                 btrfs_set_inode_ref_index(path->nodes[0], ref, index);
 100                 ptr = (unsigned long)(ref + 1);
 101         }
 102         write_extent_buffer(path->nodes[0], name, ptr, name_len);
 103         btrfs_mark_buffer_dirty(path->nodes[0]);
 104
 105 out:
 106         btrfs_free_path(path);
 107
 108         if (ret == -EMLINK) {
 109                 if (btrfs_fs_incompat(root->fs_info,
 110                                       BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF))
 111                         ret = btrfs_insert_inode_extref(trans, root, name,
 112                                                         name_len,
 113                                                         inode_objectid,
 114                                                         ref_objectid, index);
 115         }
 116         return ret;
 117 }
 118
 119 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 120                        *root, struct btrfs_path *path,
 121                        struct btrfs_key *location, int mod)
 122 {
 123         int ins_len = mod < 0 ? -1 : 0;
 124         int cow = mod != 0;
 125         int ret;
 126         int slot;
 127         struct extent_buffer *leaf;
 128         struct btrfs_key found_key;
 129
 130         ret = btrfs_search_slot(trans, root, location, path, ins_len, cow);
 131         if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY &&
 132             location->offset == (u64)-1 && path->slots[0] != 0) {
 133                 slot = path->slots[0] - 1;
 134                 leaf = path->nodes[0];
 135                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
 136                 if (found_key.objectid == location->objectid &&
 137                     btrfs_key_type(&found_key) == btrfs_key_type(location)) {
 138                         path->slots[0]--;
 139                         return 0;
 140                 }
 141         }
 142         return ret;
 143 }
 144
 145 int btrfs_insert_inode(struct btrfs_trans_handle *trans, struct btrfs_root
 146                        *root, u64 objectid, struct btrfs_inode_item
 147                        *inode_item)
 148 {
 149         int ret;
 150         struct btrfs_key key;
 151
 152         key.objectid = objectid;
 153         key.type = BTRFS_INODE_ITEM_KEY;
 154         key.offset = 0;
 155
 156         ret = btrfs_insert_item(trans, root, &key, inode_item,
 157                                 sizeof(*inode_item));
 158         return ret;
 159 }
 160
 161 struct btrfs_inode_ref *btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans,
 162                 struct btrfs_root *root, struct btrfs_path *path,
 163                 const char *name, int namelen, u64 ino, u64 parent_ino,
 164                 u64 index, int ins_len)
 165 {
 166         struct btrfs_key key;
 167         struct btrfs_inode_ref *ret_inode_ref = NULL;
 168         int ret = 0;
 169
 170         key.objectid = ino;
 171         key.type = BTRFS_INODE_REF_KEY;
 172         key.offset = parent_ino;
 173
 174         ret = btrfs_search_slot(trans, root, &key, path, ins_len,
 175                                 ins_len ? 1 : 0);
 176         if (ret)
 177                 goto out;
 178
 179         find_name_in_backref(path, name, namelen, &ret_inode_ref);
 180 out:
 181         if (ret < 0)
 182                 return ERR_PTR(ret);
 183         else
 184                 return ret_inode_ref;
 185 }
 186
 187 static inline u64 btrfs_extref_hash(u64 parent_ino, const char *name,
 188                                     int namelen)
 189 {
 190         return (u64)btrfs_crc32c(parent_ino, name, namelen);
 191 }
 192
 193 static int btrfs_find_name_in_ext_backref(struct btrfs_path *path,
 194                 u64 parent_ino, const char *name, int namelen,
 195                 struct btrfs_inode_extref **extref_ret)
 196 {
 197         struct extent_buffer *node;
 198         struct btrfs_inode_extref *extref;
 199         unsigned long ptr;
 200         unsigned long name_ptr;
 201         u32 item_size;
 202         u32 cur_offset = 0;
 203         int ref_name_len;
 204         int slot;
 205
 206         node = path->nodes[0];
 207         slot = path->slots[0];
 208         item_size = btrfs_item_size_nr(node, slot);
 209         ptr = btrfs_item_ptr_offset(node, slot);
 210
 211         /*
 212          * Search all extended backrefs in this item. We're only looking
 213          * through any collisions so most of the time this is just going to
 214          * compare against one buffer. If all is well, we'll return success and
 215          * the inode ref object.
 216          */
 217         while (cur_offset < item_size) {
 218                 extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
 219                 name_ptr = (unsigned long)(&extref->name);
 220                 ref_name_len = btrfs_inode_extref_name_len(node, extref);
 221
 222                 if (ref_name_len == namelen &&
 223                     btrfs_inode_extref_parent(node, extref) == parent_ino &&
 224                     (memcmp_extent_buffer(node, name, name_ptr, namelen) == 0))
 225                 {
 226                         if (extref_ret)
 227                                 *extref_ret = extref;
 228                         return 1;
 229                 }
 230
 231                 cur_offset += ref_name_len + sizeof(*extref);
 232         }
 233
 234         return 0;
 235 }
 236
 237 struct btrfs_inode_extref *btrfs_lookup_inode_extref(struct btrfs_trans_handle
 238                 *trans, struct btrfs_path *path, struct btrfs_root *root,
 239                 u64 ino, u64 parent_ino, u64 index, const char *name,
 240                 int namelen, int ins_len)
 241 {
 242         struct btrfs_key key;
 243         struct btrfs_inode_extref *extref;
 244         int ret = 0;
 245
 246         key.objectid = ino;
 247         key.type = BTRFS_INODE_EXTREF_KEY;
 248         key.offset = btrfs_extref_hash(parent_ino, name, namelen);
 249
 250         ret = btrfs_search_slot(trans, root, &key, path, ins_len,
 251                         ins_len ? 1 : 0);
 252         if (ret < 0)
 253                 return ERR_PTR(ret);
 254         if (ret > 0)
 255                 return NULL;
 256         if (!btrfs_find_name_in_ext_backref(path, parent_ino, name,
 257                                             namelen, &extref))
 258                 return NULL;
 259
 260         return extref;
 261 }
 262
 263 int btrfs_del_inode_extref(struct btrfs_trans_handle *trans,
 264                            struct btrfs_root *root,
 265                            const char *name, int name_len,
 266                            u64 inode_objectid, u64 ref_objectid,
 267                            u64 *index)
 268 {
 269         struct btrfs_path *path;
 270         struct btrfs_key key;
 271         struct btrfs_inode_extref *extref;
 272         struct extent_buffer *leaf;
 273         int ret;
 274         int del_len = name_len + sizeof(*extref);
 275         unsigned long ptr;
 276         unsigned long item_start;
 277         u32 item_size;
 278
 279         key.objectid = inode_objectid;
 280         key.type = BTRFS_INODE_EXTREF_KEY;
 281         key.offset = btrfs_extref_hash(ref_objectid, name, name_len);
 282
 283         path = btrfs_alloc_path();
 284         if (!path)
 285                 return -ENOMEM;
 286
 287         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 288         if (ret > 0)
 289                 ret = -ENOENT;
 290         if (ret < 0)
 291                 goto out;
 292
 293         /*
 294          * Sanity check - did we find the right item for this name?  This
 295          * should always succeed so error here will make the FS readonly.
 296          */
 297         if (!btrfs_find_name_in_ext_backref(path, ref_objectid,
 298                                             name, name_len, &extref)) {
 299                 ret = -ENOENT;
 300                 goto out;
 301         }
 302
 303         leaf = path->nodes[0];
 304         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 305         if (index)
 306                 *index = btrfs_inode_extref_index(leaf, extref);
 307
 308         if (del_len == item_size) {
 309                 /*
 310                  * Common case only one ref in the item, remove the whole item.
 311                  */
 312                 ret = btrfs_del_item(trans, root, path);
 313                 goto out;
 314         }
 315
 316         ptr = (unsigned long)extref;
 317         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 318
 319         memmove_extent_buffer(leaf, ptr, ptr + del_len,
 320                               item_size - (ptr + del_len - item_start));
 321
 322         btrfs_truncate_item(trans, root, path, item_size - del_len, 1);
 323
 324 out:
 325         btrfs_free_path(path);
 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 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         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
 368         if (ret < 0)
 369                 goto out;
 370
 371         leaf = path->nodes[0];
 372         item = btrfs_item_nr(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
 388         return ret;
 389 }
 390
 391 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans,
 392                         struct btrfs_root *root, const char *name, int name_len,
 393                         u64 ino, u64 parent_ino, u64 *index)
 394 {
 395         struct btrfs_path *path;
 396         struct btrfs_key key;
 397         struct btrfs_inode_ref *ref;
 398         struct extent_buffer *leaf;
 399         unsigned long ptr;
 400         unsigned long item_start;
 401         u32 item_size;
 402         u32 sub_item_len;
 403         int ret;
 404         int search_ext_refs = 0;
 405         int del_len = name_len + sizeof(*ref);
 406
 407         key.objectid = ino;
 408         key.offset = parent_ino;
 409         key.type = BTRFS_INODE_REF_KEY;
 410
 411         path = btrfs_alloc_path();
 412         if (!path)
 413                 return -ENOMEM;
 414
 415         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 416         if (ret > 0) {
 417                 ret = -ENOENT;
 418                 search_ext_refs = 1;
 419                 goto out;
 420         } else if (ret < 0) {
 421                 goto out;
 422         }
 423         if (!find_name_in_backref(path, name, name_len, &ref)) {
 424                 ret = -ENOENT;
 425                 search_ext_refs = 1;
 426                 goto out;
 427         }
 428         leaf = path->nodes[0];
 429         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 430
 431         if (index)
 432                 *index = btrfs_inode_ref_index(leaf, ref);
 433
 434         if (del_len == item_size) {
 435                 ret = btrfs_del_item(trans, root, path);
 436                 goto out;
 437         }
 438         ptr = (unsigned long)ref;
 439         sub_item_len = name_len + sizeof(*ref);
 440         item_start = btrfs_item_ptr_offset(leaf, path->slots[0]);
 441         memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
 442                               item_size - (ptr + sub_item_len - item_start));
 443         btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1);
 444         btrfs_mark_buffer_dirty(path->nodes[0]);
 445 out:
 446         btrfs_free_path(path);
 447
 448         if (search_ext_refs &&
 449             btrfs_fs_incompat(root->fs_info,
 450                     BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF)) {
 451                 /*
 452                  * No refs were found, or we could not find the name in our ref
 453                  * array. Find and remove the extended inode ref then.
 454                  */
 455                 return btrfs_del_inode_extref(trans, root, name, name_len,
 456                                               ino, parent_ino, index);
 457         }
 458
 459         return ret;
 460 }