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 23 /* 24 * insert a name into a directory, doing overflow properly if there is a hash 25 * collision. data_size indicates how big the item inserted should be. On 26 * success a struct btrfs_dir_item pointer is returned, otherwise it is 27 * an ERR_PTR. 28 * 29 * The name is not copied into the dir item, you have to do that yourself. 30 */ 31 static struct btrfs_dir_item *insert_with_overflow(struct btrfs_trans_handle 32 *trans, 33 struct btrfs_root *root, 34 struct btrfs_path *path, 35 struct btrfs_key *cpu_key, 36 u32 data_size, 37 const char *name, 38 int name_len) 39 { 40 struct btrfs_fs_info *fs_info = root->fs_info; 41 int ret; 42 char *ptr; 43 struct btrfs_item *item; 44 struct extent_buffer *leaf; 45 46 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 47 if (ret == -EEXIST) { 48 struct btrfs_dir_item *di; 49 di = btrfs_match_dir_item_name(fs_info, path, name, name_len); 50 if (di) 51 return ERR_PTR(-EEXIST); 52 btrfs_extend_item(fs_info, path, data_size); 53 } else if (ret < 0) 54 return ERR_PTR(ret); 55 WARN_ON(ret > 0); 56 leaf = path->nodes[0]; 57 item = btrfs_item_nr(path->slots[0]); 58 ptr = btrfs_item_ptr(leaf, path->slots[0], char); 59 BUG_ON(data_size > btrfs_item_size(leaf, item)); 60 ptr += btrfs_item_size(leaf, item) - data_size; 61 return (struct btrfs_dir_item *)ptr; 62 } 63 64 /* 65 * xattrs work a lot like directories, this inserts an xattr item 66 * into the tree 67 */ 68 int btrfs_insert_xattr_item(struct btrfs_trans_handle *trans, 69 struct btrfs_root *root, 70 struct btrfs_path *path, u64 objectid, 71 const char *name, u16 name_len, 72 const void *data, u16 data_len) 73 { 74 int ret = 0; 75 struct btrfs_dir_item *dir_item; 76 unsigned long name_ptr, data_ptr; 77 struct btrfs_key key, location; 78 struct btrfs_disk_key disk_key; 79 struct extent_buffer *leaf; 80 u32 data_size; 81 82 if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(root->fs_info)) 83 return -ENOSPC; 84 85 key.objectid = objectid; 86 key.type = BTRFS_XATTR_ITEM_KEY; 87 key.offset = btrfs_name_hash(name, name_len); 88 89 data_size = sizeof(*dir_item) + name_len + data_len; 90 dir_item = insert_with_overflow(trans, root, path, &key, data_size, 91 name, name_len); 92 if (IS_ERR(dir_item)) 93 return PTR_ERR(dir_item); 94 memset(&location, 0, sizeof(location)); 95 96 leaf = path->nodes[0]; 97 btrfs_cpu_key_to_disk(&disk_key, &location); 98 btrfs_set_dir_item_key(leaf, dir_item, &disk_key); 99 btrfs_set_dir_type(leaf, dir_item, BTRFS_FT_XATTR); 100 btrfs_set_dir_name_len(leaf, dir_item, name_len); 101 btrfs_set_dir_transid(leaf, dir_item, trans->transid); 102 btrfs_set_dir_data_len(leaf, dir_item, data_len); 103 name_ptr = (unsigned long)(dir_item + 1); 104 data_ptr = (unsigned long)((char *)name_ptr + name_len); 105 106 write_extent_buffer(leaf, name, name_ptr, name_len); 107 write_extent_buffer(leaf, data, data_ptr, data_len); 108 btrfs_mark_buffer_dirty(path->nodes[0]); 109 110 return ret; 111 } 112 113 /* 114 * insert a directory item in the tree, doing all the magic for 115 * both indexes. 'dir' indicates which objectid to insert it into, 116 * 'location' is the key to stuff into the directory item, 'type' is the 117 * type of the inode we're pointing to, and 'index' is the sequence number 118 * to use for the second index (if one is created). 119 * Will return 0 or -ENOMEM 120 */ 121 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root 122 *root, const char *name, int name_len, 123 struct btrfs_inode *dir, struct btrfs_key *location, 124 u8 type, u64 index) 125 { 126 int ret = 0; 127 int ret2 = 0; 128 struct btrfs_path *path; 129 struct btrfs_dir_item *dir_item; 130 struct extent_buffer *leaf; 131 unsigned long name_ptr; 132 struct btrfs_key key; 133 struct btrfs_disk_key disk_key; 134 u32 data_size; 135 136 key.objectid = btrfs_ino(dir); 137 key.type = BTRFS_DIR_ITEM_KEY; 138 key.offset = btrfs_name_hash(name, name_len); 139 140 path = btrfs_alloc_path(); 141 if (!path) 142 return -ENOMEM; 143 path->leave_spinning = 1; 144 145 btrfs_cpu_key_to_disk(&disk_key, location); 146 147 data_size = sizeof(*dir_item) + name_len; 148 dir_item = insert_with_overflow(trans, root, path, &key, data_size, 149 name, name_len); 150 if (IS_ERR(dir_item)) { 151 ret = PTR_ERR(dir_item); 152 if (ret == -EEXIST) 153 goto second_insert; 154 goto out_free; 155 } 156 157 leaf = path->nodes[0]; 158 btrfs_set_dir_item_key(leaf, dir_item, &disk_key); 159 btrfs_set_dir_type(leaf, dir_item, type); 160 btrfs_set_dir_data_len(leaf, dir_item, 0); 161 btrfs_set_dir_name_len(leaf, dir_item, name_len); 162 btrfs_set_dir_transid(leaf, dir_item, trans->transid); 163 name_ptr = (unsigned long)(dir_item + 1); 164 165 write_extent_buffer(leaf, name, name_ptr, name_len); 166 btrfs_mark_buffer_dirty(leaf); 167 168 second_insert: 169 /* FIXME, use some real flag for selecting the extra index */ 170 if (root == root->fs_info->tree_root) { 171 ret = 0; 172 goto out_free; 173 } 174 btrfs_release_path(path); 175 176 ret2 = btrfs_insert_delayed_dir_index(trans, root->fs_info, name, 177 name_len, dir, &disk_key, type, index); 178 out_free: 179 btrfs_free_path(path); 180 if (ret) 181 return ret; 182 if (ret2) 183 return ret2; 184 return 0; 185 } 186 187 /* 188 * lookup a directory item based on name. 'dir' is the objectid 189 * we're searching in, and 'mod' tells us if you plan on deleting the 190 * item (use mod < 0) or changing the options (use mod > 0) 191 */ 192 struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans, 193 struct btrfs_root *root, 194 struct btrfs_path *path, u64 dir, 195 const char *name, int name_len, 196 int mod) 197 { 198 int ret; 199 struct btrfs_key key; 200 int ins_len = mod < 0 ? -1 : 0; 201 int cow = mod != 0; 202 203 key.objectid = dir; 204 key.type = BTRFS_DIR_ITEM_KEY; 205 206 key.offset = btrfs_name_hash(name, name_len); 207 208 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 209 if (ret < 0) 210 return ERR_PTR(ret); 211 if (ret > 0) 212 return NULL; 213 214 return btrfs_match_dir_item_name(root->fs_info, path, name, name_len); 215 } 216 217 int btrfs_check_dir_item_collision(struct btrfs_root *root, u64 dir, 218 const char *name, int name_len) 219 { 220 int ret; 221 struct btrfs_key key; 222 struct btrfs_dir_item *di; 223 int data_size; 224 struct extent_buffer *leaf; 225 int slot; 226 struct btrfs_path *path; 227 228 229 path = btrfs_alloc_path(); 230 if (!path) 231 return -ENOMEM; 232 233 key.objectid = dir; 234 key.type = BTRFS_DIR_ITEM_KEY; 235 key.offset = btrfs_name_hash(name, name_len); 236 237 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 238 239 /* return back any errors */ 240 if (ret < 0) 241 goto out; 242 243 /* nothing found, we're safe */ 244 if (ret > 0) { 245 ret = 0; 246 goto out; 247 } 248 249 /* we found an item, look for our name in the item */ 250 di = btrfs_match_dir_item_name(root->fs_info, path, name, name_len); 251 if (di) { 252 /* our exact name was found */ 253 ret = -EEXIST; 254 goto out; 255 } 256 257 /* 258 * see if there is room in the item to insert this 259 * name 260 */ 261 data_size = sizeof(*di) + name_len; 262 leaf = path->nodes[0]; 263 slot = path->slots[0]; 264 if (data_size + btrfs_item_size_nr(leaf, slot) + 265 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root->fs_info)) { 266 ret = -EOVERFLOW; 267 } else { 268 /* plenty of insertion room */ 269 ret = 0; 270 } 271 out: 272 btrfs_free_path(path); 273 return ret; 274 } 275 276 /* 277 * lookup a directory item based on index. 'dir' is the objectid 278 * we're searching in, and 'mod' tells us if you plan on deleting the 279 * item (use mod < 0) or changing the options (use mod > 0) 280 * 281 * The name is used to make sure the index really points to the name you were 282 * looking for. 283 */ 284 struct btrfs_dir_item * 285 btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans, 286 struct btrfs_root *root, 287 struct btrfs_path *path, u64 dir, 288 u64 objectid, const char *name, int name_len, 289 int mod) 290 { 291 int ret; 292 struct btrfs_key key; 293 int ins_len = mod < 0 ? -1 : 0; 294 int cow = mod != 0; 295 296 key.objectid = dir; 297 key.type = BTRFS_DIR_INDEX_KEY; 298 key.offset = objectid; 299 300 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 301 if (ret < 0) 302 return ERR_PTR(ret); 303 if (ret > 0) 304 return ERR_PTR(-ENOENT); 305 return btrfs_match_dir_item_name(root->fs_info, path, name, name_len); 306 } 307 308 struct btrfs_dir_item * 309 btrfs_search_dir_index_item(struct btrfs_root *root, 310 struct btrfs_path *path, u64 dirid, 311 const char *name, int name_len) 312 { 313 struct extent_buffer *leaf; 314 struct btrfs_dir_item *di; 315 struct btrfs_key key; 316 u32 nritems; 317 int ret; 318 319 key.objectid = dirid; 320 key.type = BTRFS_DIR_INDEX_KEY; 321 key.offset = 0; 322 323 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 324 if (ret < 0) 325 return ERR_PTR(ret); 326 327 leaf = path->nodes[0]; 328 nritems = btrfs_header_nritems(leaf); 329 330 while (1) { 331 if (path->slots[0] >= nritems) { 332 ret = btrfs_next_leaf(root, path); 333 if (ret < 0) 334 return ERR_PTR(ret); 335 if (ret > 0) 336 break; 337 leaf = path->nodes[0]; 338 nritems = btrfs_header_nritems(leaf); 339 continue; 340 } 341 342 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 343 if (key.objectid != dirid || key.type != BTRFS_DIR_INDEX_KEY) 344 break; 345 346 di = btrfs_match_dir_item_name(root->fs_info, path, 347 name, name_len); 348 if (di) 349 return di; 350 351 path->slots[0]++; 352 } 353 return NULL; 354 } 355 356 struct btrfs_dir_item *btrfs_lookup_xattr(struct btrfs_trans_handle *trans, 357 struct btrfs_root *root, 358 struct btrfs_path *path, u64 dir, 359 const char *name, u16 name_len, 360 int mod) 361 { 362 int ret; 363 struct btrfs_key key; 364 int ins_len = mod < 0 ? -1 : 0; 365 int cow = mod != 0; 366 367 key.objectid = dir; 368 key.type = BTRFS_XATTR_ITEM_KEY; 369 key.offset = btrfs_name_hash(name, name_len); 370 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 371 if (ret < 0) 372 return ERR_PTR(ret); 373 if (ret > 0) 374 return NULL; 375 376 return btrfs_match_dir_item_name(root->fs_info, path, name, name_len); 377 } 378 379 /* 380 * helper function to look at the directory item pointed to by 'path' 381 * this walks through all the entries in a dir item and finds one 382 * for a specific name. 383 */ 384 struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_fs_info *fs_info, 385 struct btrfs_path *path, 386 const char *name, int name_len) 387 { 388 struct btrfs_dir_item *dir_item; 389 unsigned long name_ptr; 390 u32 total_len; 391 u32 cur = 0; 392 u32 this_len; 393 struct extent_buffer *leaf; 394 395 leaf = path->nodes[0]; 396 dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item); 397 398 total_len = btrfs_item_size_nr(leaf, path->slots[0]); 399 while (cur < total_len) { 400 this_len = sizeof(*dir_item) + 401 btrfs_dir_name_len(leaf, dir_item) + 402 btrfs_dir_data_len(leaf, dir_item); 403 name_ptr = (unsigned long)(dir_item + 1); 404 405 if (btrfs_dir_name_len(leaf, dir_item) == name_len && 406 memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) 407 return dir_item; 408 409 cur += this_len; 410 dir_item = (struct btrfs_dir_item *)((char *)dir_item + 411 this_len); 412 } 413 return NULL; 414 } 415 416 /* 417 * given a pointer into a directory item, delete it. This 418 * handles items that have more than one entry in them. 419 */ 420 int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans, 421 struct btrfs_root *root, 422 struct btrfs_path *path, 423 struct btrfs_dir_item *di) 424 { 425 426 struct extent_buffer *leaf; 427 u32 sub_item_len; 428 u32 item_len; 429 int ret = 0; 430 431 leaf = path->nodes[0]; 432 sub_item_len = sizeof(*di) + btrfs_dir_name_len(leaf, di) + 433 btrfs_dir_data_len(leaf, di); 434 item_len = btrfs_item_size_nr(leaf, path->slots[0]); 435 if (sub_item_len == item_len) { 436 ret = btrfs_del_item(trans, root, path); 437 } else { 438 /* MARKER */ 439 unsigned long ptr = (unsigned long)di; 440 unsigned long start; 441 442 start = btrfs_item_ptr_offset(leaf, path->slots[0]); 443 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 444 item_len - (ptr + sub_item_len - start)); 445 btrfs_truncate_item(root->fs_info, path, 446 item_len - sub_item_len, 1); 447 } 448 return ret; 449 } 450