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 /* Returns NULL if no extref found */ 95 struct btrfs_inode_extref * 96 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, 97 struct btrfs_root *root, 98 struct btrfs_path *path, 99 const char *name, int name_len, 100 u64 inode_objectid, u64 ref_objectid, int ins_len, 101 int cow) 102 { 103 int ret; 104 struct btrfs_key key; 105 struct btrfs_inode_extref *extref; 106 107 key.objectid = inode_objectid; 108 key.type = BTRFS_INODE_EXTREF_KEY; 109 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 110 111 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 112 if (ret < 0) 113 return ERR_PTR(ret); 114 if (ret > 0) 115 return NULL; 116 if (!btrfs_find_name_in_ext_backref(path, ref_objectid, name, name_len, &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 btrfs_set_key_type(&key, 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, ref_objectid, 159 name, name_len, &extref)) { 160 btrfs_std_error(root->fs_info, -ENOENT); 161 ret = -EROFS; 162 goto out; 163 } 164 165 leaf = path->nodes[0]; 166 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 167 if (index) 168 *index = btrfs_inode_extref_index(leaf, extref); 169 170 if (del_len == item_size) { 171 /* 172 * Common case only one ref in the item, remove the 173 * whole item. 174 */ 175 ret = btrfs_del_item(trans, root, path); 176 goto out; 177 } 178 179 ptr = (unsigned long)extref; 180 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 181 182 memmove_extent_buffer(leaf, ptr, ptr + del_len, 183 item_size - (ptr + del_len - item_start)); 184 185 btrfs_truncate_item(root, path, item_size - del_len, 1); 186 187 out: 188 btrfs_free_path(path); 189 190 return ret; 191 } 192 193 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 194 struct btrfs_root *root, 195 const char *name, int name_len, 196 u64 inode_objectid, u64 ref_objectid, u64 *index) 197 { 198 struct btrfs_path *path; 199 struct btrfs_key key; 200 struct btrfs_inode_ref *ref; 201 struct extent_buffer *leaf; 202 unsigned long ptr; 203 unsigned long item_start; 204 u32 item_size; 205 u32 sub_item_len; 206 int ret; 207 int search_ext_refs = 0; 208 int del_len = name_len + sizeof(*ref); 209 210 key.objectid = inode_objectid; 211 key.offset = ref_objectid; 212 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 213 214 path = btrfs_alloc_path(); 215 if (!path) 216 return -ENOMEM; 217 218 path->leave_spinning = 1; 219 220 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 221 if (ret > 0) { 222 ret = -ENOENT; 223 search_ext_refs = 1; 224 goto out; 225 } else if (ret < 0) { 226 goto out; 227 } 228 if (!find_name_in_backref(path, name, name_len, &ref)) { 229 ret = -ENOENT; 230 search_ext_refs = 1; 231 goto out; 232 } 233 leaf = path->nodes[0]; 234 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 235 236 if (index) 237 *index = btrfs_inode_ref_index(leaf, ref); 238 239 if (del_len == item_size) { 240 ret = btrfs_del_item(trans, root, path); 241 goto out; 242 } 243 ptr = (unsigned long)ref; 244 sub_item_len = name_len + sizeof(*ref); 245 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 246 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 247 item_size - (ptr + sub_item_len - item_start)); 248 btrfs_truncate_item(root, path, item_size - sub_item_len, 1); 249 out: 250 btrfs_free_path(path); 251 252 if (search_ext_refs) { 253 /* 254 * No refs were found, or we could not find the 255 * name in our ref array. Find and remove the extended 256 * inode ref then. 257 */ 258 return btrfs_del_inode_extref(trans, root, name, name_len, 259 inode_objectid, ref_objectid, index); 260 } 261 262 return ret; 263 } 264 265 /* 266 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 267 * 268 * The caller must have checked against BTRFS_LINK_MAX already. 269 */ 270 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 271 struct btrfs_root *root, 272 const char *name, int name_len, 273 u64 inode_objectid, u64 ref_objectid, u64 index) 274 { 275 struct btrfs_inode_extref *extref; 276 int ret; 277 int ins_len = name_len + sizeof(*extref); 278 unsigned long ptr; 279 struct btrfs_path *path; 280 struct btrfs_key key; 281 struct extent_buffer *leaf; 282 struct btrfs_item *item; 283 284 key.objectid = inode_objectid; 285 key.type = BTRFS_INODE_EXTREF_KEY; 286 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 287 288 path = btrfs_alloc_path(); 289 if (!path) 290 return -ENOMEM; 291 292 path->leave_spinning = 1; 293 ret = btrfs_insert_empty_item(trans, root, path, &key, 294 ins_len); 295 if (ret == -EEXIST) { 296 if (btrfs_find_name_in_ext_backref(path, ref_objectid, 297 name, name_len, NULL)) 298 goto out; 299 300 btrfs_extend_item(root, path, ins_len); 301 ret = 0; 302 } 303 if (ret < 0) 304 goto out; 305 306 leaf = path->nodes[0]; 307 item = btrfs_item_nr(path->slots[0]); 308 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 309 ptr += btrfs_item_size(leaf, item) - ins_len; 310 extref = (struct btrfs_inode_extref *)ptr; 311 312 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 313 btrfs_set_inode_extref_index(path->nodes[0], extref, index); 314 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 315 316 ptr = (unsigned long)&extref->name; 317 write_extent_buffer(path->nodes[0], name, ptr, name_len); 318 btrfs_mark_buffer_dirty(path->nodes[0]); 319 320 out: 321 btrfs_free_path(path); 322 return ret; 323 } 324 325 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 326 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 327 struct btrfs_root *root, 328 const char *name, int name_len, 329 u64 inode_objectid, u64 ref_objectid, u64 index) 330 { 331 struct btrfs_path *path; 332 struct btrfs_key key; 333 struct btrfs_inode_ref *ref; 334 unsigned long ptr; 335 int ret; 336 int ins_len = name_len + sizeof(*ref); 337 338 key.objectid = inode_objectid; 339 key.offset = ref_objectid; 340 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 341 342 path = btrfs_alloc_path(); 343 if (!path) 344 return -ENOMEM; 345 346 path->leave_spinning = 1; 347 ret = btrfs_insert_empty_item(trans, root, path, &key, 348 ins_len); 349 if (ret == -EEXIST) { 350 u32 old_size; 351 352 if (find_name_in_backref(path, name, name_len, &ref)) 353 goto out; 354 355 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]); 356 btrfs_extend_item(root, path, ins_len); 357 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 358 struct btrfs_inode_ref); 359 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 360 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 361 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 362 ptr = (unsigned long)(ref + 1); 363 ret = 0; 364 } else if (ret < 0) { 365 if (ret == -EOVERFLOW) 366 ret = -EMLINK; 367 goto out; 368 } else { 369 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 370 struct btrfs_inode_ref); 371 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 372 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 373 ptr = (unsigned long)(ref + 1); 374 } 375 write_extent_buffer(path->nodes[0], name, ptr, name_len); 376 btrfs_mark_buffer_dirty(path->nodes[0]); 377 378 out: 379 btrfs_free_path(path); 380 381 if (ret == -EMLINK) { 382 struct btrfs_super_block *disk_super = root->fs_info->super_copy; 383 /* We ran out of space in the ref array. Need to 384 * add an extended ref. */ 385 if (btrfs_super_incompat_flags(disk_super) 386 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 387 ret = btrfs_insert_inode_extref(trans, root, name, 388 name_len, 389 inode_objectid, 390 ref_objectid, index); 391 } 392 393 return ret; 394 } 395 396 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 397 struct btrfs_root *root, 398 struct btrfs_path *path, u64 objectid) 399 { 400 struct btrfs_key key; 401 int ret; 402 key.objectid = objectid; 403 btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY); 404 key.offset = 0; 405 406 ret = btrfs_insert_empty_item(trans, root, path, &key, 407 sizeof(struct btrfs_inode_item)); 408 return ret; 409 } 410 411 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 412 *root, struct btrfs_path *path, 413 struct btrfs_key *location, int mod) 414 { 415 int ins_len = mod < 0 ? -1 : 0; 416 int cow = mod != 0; 417 int ret; 418 int slot; 419 struct extent_buffer *leaf; 420 struct btrfs_key found_key; 421 422 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 423 if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY && 424 location->offset == (u64)-1 && path->slots[0] != 0) { 425 slot = path->slots[0] - 1; 426 leaf = path->nodes[0]; 427 btrfs_item_key_to_cpu(leaf, &found_key, slot); 428 if (found_key.objectid == location->objectid && 429 btrfs_key_type(&found_key) == btrfs_key_type(location)) { 430 path->slots[0]--; 431 return 0; 432 } 433 } 434 return ret; 435 } 436