~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/free-space-cache.c

Version: ~ [ linux-5.14-rc3 ] ~ [ linux-5.13.5 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.53 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.135 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.198 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.240 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.276 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.276 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Copyright (C) 2008 Red Hat.  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 <linux/pagemap.h>
 20 #include <linux/sched.h>
 21 #include <linux/slab.h>
 22 #include <linux/math64.h>
 23 #include <linux/ratelimit.h>
 24 #include "ctree.h"
 25 #include "free-space-cache.h"
 26 #include "transaction.h"
 27 #include "disk-io.h"
 28 #include "extent_io.h"
 29 #include "inode-map.h"
 30 
 31 #define BITS_PER_BITMAP         (PAGE_CACHE_SIZE * 8)
 32 #define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
 33 
 34 static int link_free_space(struct btrfs_free_space_ctl *ctl,
 35                            struct btrfs_free_space *info);
 36 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 37                               struct btrfs_free_space *info);
 38 
 39 static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
 40                                                struct btrfs_path *path,
 41                                                u64 offset)
 42 {
 43         struct btrfs_key key;
 44         struct btrfs_key location;
 45         struct btrfs_disk_key disk_key;
 46         struct btrfs_free_space_header *header;
 47         struct extent_buffer *leaf;
 48         struct inode *inode = NULL;
 49         int ret;
 50 
 51         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 52         key.offset = offset;
 53         key.type = 0;
 54 
 55         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 56         if (ret < 0)
 57                 return ERR_PTR(ret);
 58         if (ret > 0) {
 59                 btrfs_release_path(path);
 60                 return ERR_PTR(-ENOENT);
 61         }
 62 
 63         leaf = path->nodes[0];
 64         header = btrfs_item_ptr(leaf, path->slots[0],
 65                                 struct btrfs_free_space_header);
 66         btrfs_free_space_key(leaf, header, &disk_key);
 67         btrfs_disk_key_to_cpu(&location, &disk_key);
 68         btrfs_release_path(path);
 69 
 70         inode = btrfs_iget(root->fs_info->sb, &location, root, NULL);
 71         if (!inode)
 72                 return ERR_PTR(-ENOENT);
 73         if (IS_ERR(inode))
 74                 return inode;
 75         if (is_bad_inode(inode)) {
 76                 iput(inode);
 77                 return ERR_PTR(-ENOENT);
 78         }
 79 
 80         mapping_set_gfp_mask(inode->i_mapping,
 81                         mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
 82 
 83         return inode;
 84 }
 85 
 86 struct inode *lookup_free_space_inode(struct btrfs_root *root,
 87                                       struct btrfs_block_group_cache
 88                                       *block_group, struct btrfs_path *path)
 89 {
 90         struct inode *inode = NULL;
 91         u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
 92 
 93         spin_lock(&block_group->lock);
 94         if (block_group->inode)
 95                 inode = igrab(block_group->inode);
 96         spin_unlock(&block_group->lock);
 97         if (inode)
 98                 return inode;
 99 
100         inode = __lookup_free_space_inode(root, path,
101                                           block_group->key.objectid);
102         if (IS_ERR(inode))
103                 return inode;
104 
105         spin_lock(&block_group->lock);
106         if (!((BTRFS_I(inode)->flags & flags) == flags)) {
107                 btrfs_info(root->fs_info,
108                         "Old style space inode found, converting.");
109                 BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
110                         BTRFS_INODE_NODATACOW;
111                 block_group->disk_cache_state = BTRFS_DC_CLEAR;
112         }
113 
114         if (!block_group->iref) {
115                 block_group->inode = igrab(inode);
116                 block_group->iref = 1;
117         }
118         spin_unlock(&block_group->lock);
119 
120         return inode;
121 }
122 
123 static int __create_free_space_inode(struct btrfs_root *root,
124                                      struct btrfs_trans_handle *trans,
125                                      struct btrfs_path *path,
126                                      u64 ino, u64 offset)
127 {
128         struct btrfs_key key;
129         struct btrfs_disk_key disk_key;
130         struct btrfs_free_space_header *header;
131         struct btrfs_inode_item *inode_item;
132         struct extent_buffer *leaf;
133         u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
134         int ret;
135 
136         ret = btrfs_insert_empty_inode(trans, root, path, ino);
137         if (ret)
138                 return ret;
139 
140         /* We inline crc's for the free disk space cache */
141         if (ino != BTRFS_FREE_INO_OBJECTID)
142                 flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
143 
144         leaf = path->nodes[0];
145         inode_item = btrfs_item_ptr(leaf, path->slots[0],
146                                     struct btrfs_inode_item);
147         btrfs_item_key(leaf, &disk_key, path->slots[0]);
148         memset_extent_buffer(leaf, 0, (unsigned long)inode_item,
149                              sizeof(*inode_item));
150         btrfs_set_inode_generation(leaf, inode_item, trans->transid);
151         btrfs_set_inode_size(leaf, inode_item, 0);
152         btrfs_set_inode_nbytes(leaf, inode_item, 0);
153         btrfs_set_inode_uid(leaf, inode_item, 0);
154         btrfs_set_inode_gid(leaf, inode_item, 0);
155         btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
156         btrfs_set_inode_flags(leaf, inode_item, flags);
157         btrfs_set_inode_nlink(leaf, inode_item, 1);
158         btrfs_set_inode_transid(leaf, inode_item, trans->transid);
159         btrfs_set_inode_block_group(leaf, inode_item, offset);
160         btrfs_mark_buffer_dirty(leaf);
161         btrfs_release_path(path);
162 
163         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
164         key.offset = offset;
165         key.type = 0;
166 
167         ret = btrfs_insert_empty_item(trans, root, path, &key,
168                                       sizeof(struct btrfs_free_space_header));
169         if (ret < 0) {
170                 btrfs_release_path(path);
171                 return ret;
172         }
173         leaf = path->nodes[0];
174         header = btrfs_item_ptr(leaf, path->slots[0],
175                                 struct btrfs_free_space_header);
176         memset_extent_buffer(leaf, 0, (unsigned long)header, sizeof(*header));
177         btrfs_set_free_space_key(leaf, header, &disk_key);
178         btrfs_mark_buffer_dirty(leaf);
179         btrfs_release_path(path);
180 
181         return 0;
182 }
183 
184 int create_free_space_inode(struct btrfs_root *root,
185                             struct btrfs_trans_handle *trans,
186                             struct btrfs_block_group_cache *block_group,
187                             struct btrfs_path *path)
188 {
189         int ret;
190         u64 ino;
191 
192         ret = btrfs_find_free_objectid(root, &ino);
193         if (ret < 0)
194                 return ret;
195 
196         return __create_free_space_inode(root, trans, path, ino,
197                                          block_group->key.objectid);
198 }
199 
200 int btrfs_check_trunc_cache_free_space(struct btrfs_root *root,
201                                        struct btrfs_block_rsv *rsv)
202 {
203         u64 needed_bytes;
204         int ret;
205 
206         /* 1 for slack space, 1 for updating the inode */
207         needed_bytes = btrfs_calc_trunc_metadata_size(root, 1) +
208                 btrfs_calc_trans_metadata_size(root, 1);
209 
210         spin_lock(&rsv->lock);
211         if (rsv->reserved < needed_bytes)
212                 ret = -ENOSPC;
213         else
214                 ret = 0;
215         spin_unlock(&rsv->lock);
216         return ret;
217 }
218 
219 int btrfs_truncate_free_space_cache(struct btrfs_root *root,
220                                     struct btrfs_trans_handle *trans,
221                                     struct inode *inode)
222 {
223         int ret = 0;
224 
225         btrfs_i_size_write(inode, 0);
226         truncate_pagecache(inode, 0);
227 
228         /*
229          * We don't need an orphan item because truncating the free space cache
230          * will never be split across transactions.
231          */
232         ret = btrfs_truncate_inode_items(trans, root, inode,
233                                          0, BTRFS_EXTENT_DATA_KEY);
234         if (ret) {
235                 btrfs_abort_transaction(trans, root, ret);
236                 return ret;
237         }
238 
239         ret = btrfs_update_inode(trans, root, inode);
240         if (ret)
241                 btrfs_abort_transaction(trans, root, ret);
242 
243         return ret;
244 }
245 
246 static int readahead_cache(struct inode *inode)
247 {
248         struct file_ra_state *ra;
249         unsigned long last_index;
250 
251         ra = kzalloc(sizeof(*ra), GFP_NOFS);
252         if (!ra)
253                 return -ENOMEM;
254 
255         file_ra_state_init(ra, inode->i_mapping);
256         last_index = (i_size_read(inode) - 1) >> PAGE_CACHE_SHIFT;
257 
258         page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
259 
260         kfree(ra);
261 
262         return 0;
263 }
264 
265 struct io_ctl {
266         void *cur, *orig;
267         struct page *page;
268         struct page **pages;
269         struct btrfs_root *root;
270         unsigned long size;
271         int index;
272         int num_pages;
273         unsigned check_crcs:1;
274 };
275 
276 static int io_ctl_init(struct io_ctl *io_ctl, struct inode *inode,
277                        struct btrfs_root *root, int write)
278 {
279         int num_pages;
280         int check_crcs = 0;
281 
282         num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_CACHE_SIZE);
283 
284         if (btrfs_ino(inode) != BTRFS_FREE_INO_OBJECTID)
285                 check_crcs = 1;
286 
287         /* Make sure we can fit our crcs into the first page */
288         if (write && check_crcs &&
289             (num_pages * sizeof(u32)) >= PAGE_CACHE_SIZE)
290                 return -ENOSPC;
291 
292         memset(io_ctl, 0, sizeof(struct io_ctl));
293 
294         io_ctl->pages = kzalloc(sizeof(struct page *) * num_pages, GFP_NOFS);
295         if (!io_ctl->pages)
296                 return -ENOMEM;
297 
298         io_ctl->num_pages = num_pages;
299         io_ctl->root = root;
300         io_ctl->check_crcs = check_crcs;
301 
302         return 0;
303 }
304 
305 static void io_ctl_free(struct io_ctl *io_ctl)
306 {
307         kfree(io_ctl->pages);
308 }
309 
310 static void io_ctl_unmap_page(struct io_ctl *io_ctl)
311 {
312         if (io_ctl->cur) {
313                 kunmap(io_ctl->page);
314                 io_ctl->cur = NULL;
315                 io_ctl->orig = NULL;
316         }
317 }
318 
319 static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
320 {
321         ASSERT(io_ctl->index < io_ctl->num_pages);
322         io_ctl->page = io_ctl->pages[io_ctl->index++];
323         io_ctl->cur = kmap(io_ctl->page);
324         io_ctl->orig = io_ctl->cur;
325         io_ctl->size = PAGE_CACHE_SIZE;
326         if (clear)
327                 memset(io_ctl->cur, 0, PAGE_CACHE_SIZE);
328 }
329 
330 static void io_ctl_drop_pages(struct io_ctl *io_ctl)
331 {
332         int i;
333 
334         io_ctl_unmap_page(io_ctl);
335 
336         for (i = 0; i < io_ctl->num_pages; i++) {
337                 if (io_ctl->pages[i]) {
338                         ClearPageChecked(io_ctl->pages[i]);
339                         unlock_page(io_ctl->pages[i]);
340                         page_cache_release(io_ctl->pages[i]);
341                 }
342         }
343 }
344 
345 static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct inode *inode,
346                                 int uptodate)
347 {
348         struct page *page;
349         gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
350         int i;
351 
352         for (i = 0; i < io_ctl->num_pages; i++) {
353                 page = find_or_create_page(inode->i_mapping, i, mask);
354                 if (!page) {
355                         io_ctl_drop_pages(io_ctl);
356                         return -ENOMEM;
357                 }
358                 io_ctl->pages[i] = page;
359                 if (uptodate && !PageUptodate(page)) {
360                         btrfs_readpage(NULL, page);
361                         lock_page(page);
362                         if (!PageUptodate(page)) {
363                                 btrfs_err(BTRFS_I(inode)->root->fs_info,
364                                            "error reading free space cache");
365                                 io_ctl_drop_pages(io_ctl);
366                                 return -EIO;
367                         }
368                 }
369         }
370 
371         for (i = 0; i < io_ctl->num_pages; i++) {
372                 clear_page_dirty_for_io(io_ctl->pages[i]);
373                 set_page_extent_mapped(io_ctl->pages[i]);
374         }
375 
376         return 0;
377 }
378 
379 static void io_ctl_set_generation(struct io_ctl *io_ctl, u64 generation)
380 {
381         __le64 *val;
382 
383         io_ctl_map_page(io_ctl, 1);
384 
385         /*
386          * Skip the csum areas.  If we don't check crcs then we just have a
387          * 64bit chunk at the front of the first page.
388          */
389         if (io_ctl->check_crcs) {
390                 io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);
391                 io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);
392         } else {
393                 io_ctl->cur += sizeof(u64);
394                 io_ctl->size -= sizeof(u64) * 2;
395         }
396 
397         val = io_ctl->cur;
398         *val = cpu_to_le64(generation);
399         io_ctl->cur += sizeof(u64);
400 }
401 
402 static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
403 {
404         __le64 *gen;
405 
406         /*
407          * Skip the crc area.  If we don't check crcs then we just have a 64bit
408          * chunk at the front of the first page.
409          */
410         if (io_ctl->check_crcs) {
411                 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
412                 io_ctl->size -= sizeof(u64) +
413                         (sizeof(u32) * io_ctl->num_pages);
414         } else {
415                 io_ctl->cur += sizeof(u64);
416                 io_ctl->size -= sizeof(u64) * 2;
417         }
418 
419         gen = io_ctl->cur;
420         if (le64_to_cpu(*gen) != generation) {
421                 printk_ratelimited(KERN_ERR "BTRFS: space cache generation "
422                                    "(%Lu) does not match inode (%Lu)\n", *gen,
423                                    generation);
424                 io_ctl_unmap_page(io_ctl);
425                 return -EIO;
426         }
427         io_ctl->cur += sizeof(u64);
428         return 0;
429 }
430 
431 static void io_ctl_set_crc(struct io_ctl *io_ctl, int index)
432 {
433         u32 *tmp;
434         u32 crc = ~(u32)0;
435         unsigned offset = 0;
436 
437         if (!io_ctl->check_crcs) {
438                 io_ctl_unmap_page(io_ctl);
439                 return;
440         }
441 
442         if (index == 0)
443                 offset = sizeof(u32) * io_ctl->num_pages;
444 
445         crc = btrfs_csum_data(io_ctl->orig + offset, crc,
446                               PAGE_CACHE_SIZE - offset);
447         btrfs_csum_final(crc, (char *)&crc);
448         io_ctl_unmap_page(io_ctl);
449         tmp = kmap(io_ctl->pages[0]);
450         tmp += index;
451         *tmp = crc;
452         kunmap(io_ctl->pages[0]);
453 }
454 
455 static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
456 {
457         u32 *tmp, val;
458         u32 crc = ~(u32)0;
459         unsigned offset = 0;
460 
461         if (!io_ctl->check_crcs) {
462                 io_ctl_map_page(io_ctl, 0);
463                 return 0;
464         }
465 
466         if (index == 0)
467                 offset = sizeof(u32) * io_ctl->num_pages;
468 
469         tmp = kmap(io_ctl->pages[0]);
470         tmp += index;
471         val = *tmp;
472         kunmap(io_ctl->pages[0]);
473 
474         io_ctl_map_page(io_ctl, 0);
475         crc = btrfs_csum_data(io_ctl->orig + offset, crc,
476                               PAGE_CACHE_SIZE - offset);
477         btrfs_csum_final(crc, (char *)&crc);
478         if (val != crc) {
479                 printk_ratelimited(KERN_ERR "BTRFS: csum mismatch on free "
480                                    "space cache\n");
481                 io_ctl_unmap_page(io_ctl);
482                 return -EIO;
483         }
484 
485         return 0;
486 }
487 
488 static int io_ctl_add_entry(struct io_ctl *io_ctl, u64 offset, u64 bytes,
489                             void *bitmap)
490 {
491         struct btrfs_free_space_entry *entry;
492 
493         if (!io_ctl->cur)
494                 return -ENOSPC;
495 
496         entry = io_ctl->cur;
497         entry->offset = cpu_to_le64(offset);
498         entry->bytes = cpu_to_le64(bytes);
499         entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :
500                 BTRFS_FREE_SPACE_EXTENT;
501         io_ctl->cur += sizeof(struct btrfs_free_space_entry);
502         io_ctl->size -= sizeof(struct btrfs_free_space_entry);
503 
504         if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
505                 return 0;
506 
507         io_ctl_set_crc(io_ctl, io_ctl->index - 1);
508 
509         /* No more pages to map */
510         if (io_ctl->index >= io_ctl->num_pages)
511                 return 0;
512 
513         /* map the next page */
514         io_ctl_map_page(io_ctl, 1);
515         return 0;
516 }
517 
518 static int io_ctl_add_bitmap(struct io_ctl *io_ctl, void *bitmap)
519 {
520         if (!io_ctl->cur)
521                 return -ENOSPC;
522 
523         /*
524          * If we aren't at the start of the current page, unmap this one and
525          * map the next one if there is any left.
526          */
527         if (io_ctl->cur != io_ctl->orig) {
528                 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
529                 if (io_ctl->index >= io_ctl->num_pages)
530                         return -ENOSPC;
531                 io_ctl_map_page(io_ctl, 0);
532         }
533 
534         memcpy(io_ctl->cur, bitmap, PAGE_CACHE_SIZE);
535         io_ctl_set_crc(io_ctl, io_ctl->index - 1);
536         if (io_ctl->index < io_ctl->num_pages)
537                 io_ctl_map_page(io_ctl, 0);
538         return 0;
539 }
540 
541 static void io_ctl_zero_remaining_pages(struct io_ctl *io_ctl)
542 {
543         /*
544          * If we're not on the boundary we know we've modified the page and we
545          * need to crc the page.
546          */
547         if (io_ctl->cur != io_ctl->orig)
548                 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
549         else
550                 io_ctl_unmap_page(io_ctl);
551 
552         while (io_ctl->index < io_ctl->num_pages) {
553                 io_ctl_map_page(io_ctl, 1);
554                 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
555         }
556 }
557 
558 static int io_ctl_read_entry(struct io_ctl *io_ctl,
559                             struct btrfs_free_space *entry, u8 *type)
560 {
561         struct btrfs_free_space_entry *e;
562         int ret;
563 
564         if (!io_ctl->cur) {
565                 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
566                 if (ret)
567                         return ret;
568         }
569 
570         e = io_ctl->cur;
571         entry->offset = le64_to_cpu(e->offset);
572         entry->bytes = le64_to_cpu(e->bytes);
573         *type = e->type;
574         io_ctl->cur += sizeof(struct btrfs_free_space_entry);
575         io_ctl->size -= sizeof(struct btrfs_free_space_entry);
576 
577         if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
578                 return 0;
579 
580         io_ctl_unmap_page(io_ctl);
581 
582         return 0;
583 }
584 
585 static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
586                               struct btrfs_free_space *entry)
587 {
588         int ret;
589 
590         ret = io_ctl_check_crc(io_ctl, io_ctl->index);
591         if (ret)
592                 return ret;
593 
594         memcpy(entry->bitmap, io_ctl->cur, PAGE_CACHE_SIZE);
595         io_ctl_unmap_page(io_ctl);
596 
597         return 0;
598 }
599 
600 /*
601  * Since we attach pinned extents after the fact we can have contiguous sections
602  * of free space that are split up in entries.  This poses a problem with the
603  * tree logging stuff since it could have allocated across what appears to be 2
604  * entries since we would have merged the entries when adding the pinned extents
605  * back to the free space cache.  So run through the space cache that we just
606  * loaded and merge contiguous entries.  This will make the log replay stuff not
607  * blow up and it will make for nicer allocator behavior.
608  */
609 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
610 {
611         struct btrfs_free_space *e, *prev = NULL;
612         struct rb_node *n;
613 
614 again:
615         spin_lock(&ctl->tree_lock);
616         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
617                 e = rb_entry(n, struct btrfs_free_space, offset_index);
618                 if (!prev)
619                         goto next;
620                 if (e->bitmap || prev->bitmap)
621                         goto next;
622                 if (prev->offset + prev->bytes == e->offset) {
623                         unlink_free_space(ctl, prev);
624                         unlink_free_space(ctl, e);
625                         prev->bytes += e->bytes;
626                         kmem_cache_free(btrfs_free_space_cachep, e);
627                         link_free_space(ctl, prev);
628                         prev = NULL;
629                         spin_unlock(&ctl->tree_lock);
630                         goto again;
631                 }
632 next:
633                 prev = e;
634         }
635         spin_unlock(&ctl->tree_lock);
636 }
637 
638 static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
639                                    struct btrfs_free_space_ctl *ctl,
640                                    struct btrfs_path *path, u64 offset)
641 {
642         struct btrfs_free_space_header *header;
643         struct extent_buffer *leaf;
644         struct io_ctl io_ctl;
645         struct btrfs_key key;
646         struct btrfs_free_space *e, *n;
647         struct list_head bitmaps;
648         u64 num_entries;
649         u64 num_bitmaps;
650         u64 generation;
651         u8 type;
652         int ret = 0;
653 
654         INIT_LIST_HEAD(&bitmaps);
655 
656         /* Nothing in the space cache, goodbye */
657         if (!i_size_read(inode))
658                 return 0;
659 
660         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
661         key.offset = offset;
662         key.type = 0;
663 
664         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
665         if (ret < 0)
666                 return 0;
667         else if (ret > 0) {
668                 btrfs_release_path(path);
669                 return 0;
670         }
671 
672         ret = -1;
673 
674         leaf = path->nodes[0];
675         header = btrfs_item_ptr(leaf, path->slots[0],
676                                 struct btrfs_free_space_header);
677         num_entries = btrfs_free_space_entries(leaf, header);
678         num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
679         generation = btrfs_free_space_generation(leaf, header);
680         btrfs_release_path(path);
681 
682         if (!BTRFS_I(inode)->generation) {
683                 btrfs_info(root->fs_info,
684                            "The free space cache file (%llu) is invalid. skip it\n",
685                            offset);
686                 return 0;
687         }
688 
689         if (BTRFS_I(inode)->generation != generation) {
690                 btrfs_err(root->fs_info,
691                         "free space inode generation (%llu) "
692                         "did not match free space cache generation (%llu)",
693                         BTRFS_I(inode)->generation, generation);
694                 return 0;
695         }
696 
697         if (!num_entries)
698                 return 0;
699 
700         ret = io_ctl_init(&io_ctl, inode, root, 0);
701         if (ret)
702                 return ret;
703 
704         ret = readahead_cache(inode);
705         if (ret)
706                 goto out;
707 
708         ret = io_ctl_prepare_pages(&io_ctl, inode, 1);
709         if (ret)
710                 goto out;
711 
712         ret = io_ctl_check_crc(&io_ctl, 0);
713         if (ret)
714                 goto free_cache;
715 
716         ret = io_ctl_check_generation(&io_ctl, generation);
717         if (ret)
718                 goto free_cache;
719 
720         while (num_entries) {
721                 e = kmem_cache_zalloc(btrfs_free_space_cachep,
722                                       GFP_NOFS);
723                 if (!e)
724                         goto free_cache;
725 
726                 ret = io_ctl_read_entry(&io_ctl, e, &type);
727                 if (ret) {
728                         kmem_cache_free(btrfs_free_space_cachep, e);
729                         goto free_cache;
730                 }
731 
732                 if (!e->bytes) {
733                         kmem_cache_free(btrfs_free_space_cachep, e);
734                         goto free_cache;
735                 }
736 
737                 if (type == BTRFS_FREE_SPACE_EXTENT) {
738                         spin_lock(&ctl->tree_lock);
739                         ret = link_free_space(ctl, e);
740                         spin_unlock(&ctl->tree_lock);
741                         if (ret) {
742                                 btrfs_err(root->fs_info,
743                                         "Duplicate entries in free space cache, dumping");
744                                 kmem_cache_free(btrfs_free_space_cachep, e);
745                                 goto free_cache;
746                         }
747                 } else {
748                         ASSERT(num_bitmaps);
749                         num_bitmaps--;
750                         e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
751                         if (!e->bitmap) {
752                                 kmem_cache_free(
753                                         btrfs_free_space_cachep, e);
754                                 goto free_cache;
755                         }
756                         spin_lock(&ctl->tree_lock);
757                         ret = link_free_space(ctl, e);
758                         ctl->total_bitmaps++;
759                         ctl->op->recalc_thresholds(ctl);
760                         spin_unlock(&ctl->tree_lock);
761                         if (ret) {
762                                 btrfs_err(root->fs_info,
763                                         "Duplicate entries in free space cache, dumping");
764                                 kmem_cache_free(btrfs_free_space_cachep, e);
765                                 goto free_cache;
766                         }
767                         list_add_tail(&e->list, &bitmaps);
768                 }
769 
770                 num_entries--;
771         }
772 
773         io_ctl_unmap_page(&io_ctl);
774 
775         /*
776          * We add the bitmaps at the end of the entries in order that
777          * the bitmap entries are added to the cache.
778          */
779         list_for_each_entry_safe(e, n, &bitmaps, list) {
780                 list_del_init(&e->list);
781                 ret = io_ctl_read_bitmap(&io_ctl, e);
782                 if (ret)
783                         goto free_cache;
784         }
785 
786         io_ctl_drop_pages(&io_ctl);
787         merge_space_tree(ctl);
788         ret = 1;
789 out:
790         io_ctl_free(&io_ctl);
791         return ret;
792 free_cache:
793         io_ctl_drop_pages(&io_ctl);
794         __btrfs_remove_free_space_cache(ctl);
795         goto out;
796 }
797 
798 int load_free_space_cache(struct btrfs_fs_info *fs_info,
799                           struct btrfs_block_group_cache *block_group)
800 {
801         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
802         struct btrfs_root *root = fs_info->tree_root;
803         struct inode *inode;
804         struct btrfs_path *path;
805         int ret = 0;
806         bool matched;
807         u64 used = btrfs_block_group_used(&block_group->item);
808 
809         /*
810          * If this block group has been marked to be cleared for one reason or
811          * another then we can't trust the on disk cache, so just return.
812          */
813         spin_lock(&block_group->lock);
814         if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
815                 spin_unlock(&block_group->lock);
816                 return 0;
817         }
818         spin_unlock(&block_group->lock);
819 
820         path = btrfs_alloc_path();
821         if (!path)
822                 return 0;
823         path->search_commit_root = 1;
824         path->skip_locking = 1;
825 
826         inode = lookup_free_space_inode(root, block_group, path);
827         if (IS_ERR(inode)) {
828                 btrfs_free_path(path);
829                 return 0;
830         }
831 
832         /* We may have converted the inode and made the cache invalid. */
833         spin_lock(&block_group->lock);
834         if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
835                 spin_unlock(&block_group->lock);
836                 btrfs_free_path(path);
837                 goto out;
838         }
839         spin_unlock(&block_group->lock);
840 
841         ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
842                                       path, block_group->key.objectid);
843         btrfs_free_path(path);
844         if (ret <= 0)
845                 goto out;
846 
847         spin_lock(&ctl->tree_lock);
848         matched = (ctl->free_space == (block_group->key.offset - used -
849                                        block_group->bytes_super));
850         spin_unlock(&ctl->tree_lock);
851 
852         if (!matched) {
853                 __btrfs_remove_free_space_cache(ctl);
854                 btrfs_warn(fs_info, "block group %llu has wrong amount of free space",
855                         block_group->key.objectid);
856                 ret = -1;
857         }
858 out:
859         if (ret < 0) {
860                 /* This cache is bogus, make sure it gets cleared */
861                 spin_lock(&block_group->lock);
862                 block_group->disk_cache_state = BTRFS_DC_CLEAR;
863                 spin_unlock(&block_group->lock);
864                 ret = 0;
865 
866                 btrfs_warn(fs_info, "failed to load free space cache for block group %llu, rebuild it now",
867                         block_group->key.objectid);
868         }
869 
870         iput(inode);
871         return ret;
872 }
873 
874 static noinline_for_stack
875 int write_cache_extent_entries(struct io_ctl *io_ctl,
876                               struct btrfs_free_space_ctl *ctl,
877                               struct btrfs_block_group_cache *block_group,
878                               int *entries, int *bitmaps,
879                               struct list_head *bitmap_list)
880 {
881         int ret;
882         struct btrfs_free_cluster *cluster = NULL;
883         struct rb_node *node = rb_first(&ctl->free_space_offset);
884 
885         /* Get the cluster for this block_group if it exists */
886         if (block_group && !list_empty(&block_group->cluster_list)) {
887                 cluster = list_entry(block_group->cluster_list.next,
888                                      struct btrfs_free_cluster,
889                                      block_group_list);
890         }
891 
892         if (!node && cluster) {
893                 node = rb_first(&cluster->root);
894                 cluster = NULL;
895         }
896 
897         /* Write out the extent entries */
898         while (node) {
899                 struct btrfs_free_space *e;
900 
901                 e = rb_entry(node, struct btrfs_free_space, offset_index);
902                 *entries += 1;
903 
904                 ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,
905                                        e->bitmap);
906                 if (ret)
907                         goto fail;
908 
909                 if (e->bitmap) {
910                         list_add_tail(&e->list, bitmap_list);
911                         *bitmaps += 1;
912                 }
913                 node = rb_next(node);
914                 if (!node && cluster) {
915                         node = rb_first(&cluster->root);
916                         cluster = NULL;
917                 }
918         }
919         return 0;
920 fail:
921         return -ENOSPC;
922 }
923 
924 static noinline_for_stack int
925 update_cache_item(struct btrfs_trans_handle *trans,
926                   struct btrfs_root *root,
927                   struct inode *inode,
928                   struct btrfs_path *path, u64 offset,
929                   int entries, int bitmaps)
930 {
931         struct btrfs_key key;
932         struct btrfs_free_space_header *header;
933         struct extent_buffer *leaf;
934         int ret;
935 
936         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
937         key.offset = offset;
938         key.type = 0;
939 
940         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
941         if (ret < 0) {
942                 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
943                                  EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
944                                  GFP_NOFS);
945                 goto fail;
946         }
947         leaf = path->nodes[0];
948         if (ret > 0) {
949                 struct btrfs_key found_key;
950                 ASSERT(path->slots[0]);
951                 path->slots[0]--;
952                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
953                 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
954                     found_key.offset != offset) {
955                         clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
956                                          inode->i_size - 1,
957                                          EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0,
958                                          NULL, GFP_NOFS);
959                         btrfs_release_path(path);
960                         goto fail;
961                 }
962         }
963 
964         BTRFS_I(inode)->generation = trans->transid;
965         header = btrfs_item_ptr(leaf, path->slots[0],
966                                 struct btrfs_free_space_header);
967         btrfs_set_free_space_entries(leaf, header, entries);
968         btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
969         btrfs_set_free_space_generation(leaf, header, trans->transid);
970         btrfs_mark_buffer_dirty(leaf);
971         btrfs_release_path(path);
972 
973         return 0;
974 
975 fail:
976         return -1;
977 }
978 
979 static noinline_for_stack int
980 write_pinned_extent_entries(struct btrfs_root *root,
981                             struct btrfs_block_group_cache *block_group,
982                             struct io_ctl *io_ctl,
983                             int *entries)
984 {
985         u64 start, extent_start, extent_end, len;
986         struct extent_io_tree *unpin = NULL;
987         int ret;
988 
989         if (!block_group)
990                 return 0;
991 
992         /*
993          * We want to add any pinned extents to our free space cache
994          * so we don't leak the space
995          *
996          * We shouldn't have switched the pinned extents yet so this is the
997          * right one
998          */
999         unpin = root->fs_info->pinned_extents;
1000 
1001         start = block_group->key.objectid;
1002 
1003         while (start < block_group->key.objectid + block_group->key.offset) {
1004                 ret = find_first_extent_bit(unpin, start,
1005                                             &extent_start, &extent_end,
1006                                             EXTENT_DIRTY, NULL);
1007                 if (ret)
1008                         return 0;
1009 
1010                 /* This pinned extent is out of our range */
1011                 if (extent_start >= block_group->key.objectid +
1012                     block_group->key.offset)
1013                         return 0;
1014 
1015                 extent_start = max(extent_start, start);
1016                 extent_end = min(block_group->key.objectid +
1017                                  block_group->key.offset, extent_end + 1);
1018                 len = extent_end - extent_start;
1019 
1020                 *entries += 1;
1021                 ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);
1022                 if (ret)
1023                         return -ENOSPC;
1024 
1025                 start = extent_end;
1026         }
1027 
1028         return 0;
1029 }
1030 
1031 static noinline_for_stack int
1032 write_bitmap_entries(struct io_ctl *io_ctl, struct list_head *bitmap_list)
1033 {
1034         struct list_head *pos, *n;
1035         int ret;
1036 
1037         /* Write out the bitmaps */
1038         list_for_each_safe(pos, n, bitmap_list) {
1039                 struct btrfs_free_space *entry =
1040                         list_entry(pos, struct btrfs_free_space, list);
1041 
1042                 ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);
1043                 if (ret)
1044                         return -ENOSPC;
1045                 list_del_init(&entry->list);
1046         }
1047 
1048         return 0;
1049 }
1050 
1051 static int flush_dirty_cache(struct inode *inode)
1052 {
1053         int ret;
1054 
1055         ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);
1056         if (ret)
1057                 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
1058                                  EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
1059                                  GFP_NOFS);
1060 
1061         return ret;
1062 }
1063 
1064 static void noinline_for_stack
1065 cleanup_write_cache_enospc(struct inode *inode,
1066                            struct io_ctl *io_ctl,
1067                            struct extent_state **cached_state,
1068                            struct list_head *bitmap_list)
1069 {
1070         struct list_head *pos, *n;
1071 
1072         list_for_each_safe(pos, n, bitmap_list) {
1073                 struct btrfs_free_space *entry =
1074                         list_entry(pos, struct btrfs_free_space, list);
1075                 list_del_init(&entry->list);
1076         }
1077         io_ctl_drop_pages(io_ctl);
1078         unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1079                              i_size_read(inode) - 1, cached_state,
1080                              GFP_NOFS);
1081 }
1082 
1083 /**
1084  * __btrfs_write_out_cache - write out cached info to an inode
1085  * @root - the root the inode belongs to
1086  * @ctl - the free space cache we are going to write out
1087  * @block_group - the block_group for this cache if it belongs to a block_group
1088  * @trans - the trans handle
1089  * @path - the path to use
1090  * @offset - the offset for the key we'll insert
1091  *
1092  * This function writes out a free space cache struct to disk for quick recovery
1093  * on mount.  This will return 0 if it was successfull in writing the cache out,
1094  * and -1 if it was not.
1095  */
1096 static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
1097                                    struct btrfs_free_space_ctl *ctl,
1098                                    struct btrfs_block_group_cache *block_group,
1099                                    struct btrfs_trans_handle *trans,
1100                                    struct btrfs_path *path, u64 offset)
1101 {
1102         struct extent_state *cached_state = NULL;
1103         struct io_ctl io_ctl;
1104         LIST_HEAD(bitmap_list);
1105         int entries = 0;
1106         int bitmaps = 0;
1107         int ret;
1108 
1109         if (!i_size_read(inode))
1110                 return -1;
1111 
1112         ret = io_ctl_init(&io_ctl, inode, root, 1);
1113         if (ret)
1114                 return -1;
1115 
1116         if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {
1117                 down_write(&block_group->data_rwsem);
1118                 spin_lock(&block_group->lock);
1119                 if (block_group->delalloc_bytes) {
1120                         block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1121                         spin_unlock(&block_group->lock);
1122                         up_write(&block_group->data_rwsem);
1123                         BTRFS_I(inode)->generation = 0;
1124                         ret = 0;
1125                         goto out;
1126                 }
1127                 spin_unlock(&block_group->lock);
1128         }
1129 
1130         /* Lock all pages first so we can lock the extent safely. */
1131         io_ctl_prepare_pages(&io_ctl, inode, 0);
1132 
1133         lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
1134                          0, &cached_state);
1135 
1136         io_ctl_set_generation(&io_ctl, trans->transid);
1137 
1138         /* Write out the extent entries in the free space cache */
1139         ret = write_cache_extent_entries(&io_ctl, ctl,
1140                                          block_group, &entries, &bitmaps,
1141                                          &bitmap_list);
1142         if (ret)
1143                 goto out_nospc;
1144 
1145         /*
1146          * Some spaces that are freed in the current transaction are pinned,
1147          * they will be added into free space cache after the transaction is
1148          * committed, we shouldn't lose them.
1149          */
1150         ret = write_pinned_extent_entries(root, block_group, &io_ctl, &entries);
1151         if (ret)
1152                 goto out_nospc;
1153 
1154         /* At last, we write out all the bitmaps. */
1155         ret = write_bitmap_entries(&io_ctl, &bitmap_list);
1156         if (ret)
1157                 goto out_nospc;
1158 
1159         /* Zero out the rest of the pages just to make sure */
1160         io_ctl_zero_remaining_pages(&io_ctl);
1161 
1162         /* Everything is written out, now we dirty the pages in the file. */
1163         ret = btrfs_dirty_pages(root, inode, io_ctl.pages, io_ctl.num_pages,
1164                                 0, i_size_read(inode), &cached_state);
1165         if (ret)
1166                 goto out_nospc;
1167 
1168         if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1169                 up_write(&block_group->data_rwsem);
1170         /*
1171          * Release the pages and unlock the extent, we will flush
1172          * them out later
1173          */
1174         io_ctl_drop_pages(&io_ctl);
1175 
1176         unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1177                              i_size_read(inode) - 1, &cached_state, GFP_NOFS);
1178 
1179         /* Flush the dirty pages in the cache file. */
1180         ret = flush_dirty_cache(inode);
1181         if (ret)
1182                 goto out;
1183 
1184         /* Update the cache item to tell everyone this cache file is valid. */
1185         ret = update_cache_item(trans, root, inode, path, offset,
1186                                 entries, bitmaps);
1187 out:
1188         io_ctl_free(&io_ctl);
1189         if (ret) {
1190                 invalidate_inode_pages2(inode->i_mapping);
1191                 BTRFS_I(inode)->generation = 0;
1192         }
1193         btrfs_update_inode(trans, root, inode);
1194         return ret;
1195 
1196 out_nospc:
1197         cleanup_write_cache_enospc(inode, &io_ctl, &cached_state, &bitmap_list);
1198 
1199         if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1200                 up_write(&block_group->data_rwsem);
1201 
1202         goto out;
1203 }
1204 
1205 int btrfs_write_out_cache(struct btrfs_root *root,
1206                           struct btrfs_trans_handle *trans,
1207                           struct btrfs_block_group_cache *block_group,
1208                           struct btrfs_path *path)
1209 {
1210         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1211         struct inode *inode;
1212         int ret = 0;
1213 
1214         root = root->fs_info->tree_root;
1215 
1216         spin_lock(&block_group->lock);
1217         if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
1218                 spin_unlock(&block_group->lock);
1219                 return 0;
1220         }
1221 
1222         if (block_group->delalloc_bytes) {
1223                 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1224                 spin_unlock(&block_group->lock);
1225                 return 0;
1226         }
1227         spin_unlock(&block_group->lock);
1228 
1229         inode = lookup_free_space_inode(root, block_group, path);
1230         if (IS_ERR(inode))
1231                 return 0;
1232 
1233         ret = __btrfs_write_out_cache(root, inode, ctl, block_group, trans,
1234                                       path, block_group->key.objectid);
1235         if (ret) {
1236                 spin_lock(&block_group->lock);
1237                 block_group->disk_cache_state = BTRFS_DC_ERROR;
1238                 spin_unlock(&block_group->lock);
1239                 ret = 0;
1240 #ifdef DEBUG
1241                 btrfs_err(root->fs_info,
1242                         "failed to write free space cache for block group %llu",
1243                         block_group->key.objectid);
1244 #endif
1245         }
1246 
1247         iput(inode);
1248         return ret;
1249 }
1250 
1251 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
1252                                           u64 offset)
1253 {
1254         ASSERT(offset >= bitmap_start);
1255         offset -= bitmap_start;
1256         return (unsigned long)(div_u64(offset, unit));
1257 }
1258 
1259 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
1260 {
1261         return (unsigned long)(div_u64(bytes, unit));
1262 }
1263 
1264 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
1265                                    u64 offset)
1266 {
1267         u64 bitmap_start;
1268         u64 bytes_per_bitmap;
1269 
1270         bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
1271         bitmap_start = offset - ctl->start;
1272         bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
1273         bitmap_start *= bytes_per_bitmap;
1274         bitmap_start += ctl->start;
1275 
1276         return bitmap_start;
1277 }
1278 
1279 static int tree_insert_offset(struct rb_root *root, u64 offset,
1280                               struct rb_node *node, int bitmap)
1281 {
1282         struct rb_node **p = &root->rb_node;
1283         struct rb_node *parent = NULL;
1284         struct btrfs_free_space *info;
1285 
1286         while (*p) {
1287                 parent = *p;
1288                 info = rb_entry(parent, struct btrfs_free_space, offset_index);
1289 
1290                 if (offset < info->offset) {
1291                         p = &(*p)->rb_left;
1292                 } else if (offset > info->offset) {
1293                         p = &(*p)->rb_right;
1294                 } else {
1295                         /*
1296                          * we could have a bitmap entry and an extent entry
1297                          * share the same offset.  If this is the case, we want
1298                          * the extent entry to always be found first if we do a
1299                          * linear search through the tree, since we want to have
1300                          * the quickest allocation time, and allocating from an
1301                          * extent is faster than allocating from a bitmap.  So
1302                          * if we're inserting a bitmap and we find an entry at
1303                          * this offset, we want to go right, or after this entry
1304                          * logically.  If we are inserting an extent and we've
1305                          * found a bitmap, we want to go left, or before
1306                          * logically.
1307                          */
1308                         if (bitmap) {
1309                                 if (info->bitmap) {
1310                                         WARN_ON_ONCE(1);
1311                                         return -EEXIST;
1312                                 }
1313                                 p = &(*p)->rb_right;
1314                         } else {
1315                                 if (!info->bitmap) {
1316                                         WARN_ON_ONCE(1);
1317                                         return -EEXIST;
1318                                 }
1319                                 p = &(*p)->rb_left;
1320                         }
1321                 }
1322         }
1323 
1324         rb_link_node(node, parent, p);
1325         rb_insert_color(node, root);
1326 
1327         return 0;
1328 }
1329 
1330 /*
1331  * searches the tree for the given offset.
1332  *
1333  * fuzzy - If this is set, then we are trying to make an allocation, and we just
1334  * want a section that has at least bytes size and comes at or after the given
1335  * offset.
1336  */
1337 static struct btrfs_free_space *
1338 tree_search_offset(struct btrfs_free_space_ctl *ctl,
1339                    u64 offset, int bitmap_only, int fuzzy)
1340 {
1341         struct rb_node *n = ctl->free_space_offset.rb_node;
1342         struct btrfs_free_space *entry, *prev = NULL;
1343 
1344         /* find entry that is closest to the 'offset' */
1345         while (1) {
1346                 if (!n) {
1347                         entry = NULL;
1348                         break;
1349                 }
1350 
1351                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1352                 prev = entry;
1353 
1354                 if (offset < entry->offset)
1355                         n = n->rb_left;
1356                 else if (offset > entry->offset)
1357                         n = n->rb_right;
1358                 else
1359                         break;
1360         }
1361 
1362         if (bitmap_only) {
1363                 if (!entry)
1364                         return NULL;
1365                 if (entry->bitmap)
1366                         return entry;
1367 
1368                 /*
1369                  * bitmap entry and extent entry may share same offset,
1370                  * in that case, bitmap entry comes after extent entry.
1371                  */
1372                 n = rb_next(n);
1373                 if (!n)
1374                         return NULL;
1375                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1376                 if (entry->offset != offset)
1377                         return NULL;
1378 
1379                 WARN_ON(!entry->bitmap);
1380                 return entry;
1381         } else if (entry) {
1382                 if (entry->bitmap) {
1383                         /*
1384                          * if previous extent entry covers the offset,
1385                          * we should return it instead of the bitmap entry
1386                          */
1387                         n = rb_prev(&entry->offset_index);
1388                         if (n) {
1389                                 prev = rb_entry(n, struct btrfs_free_space,
1390                                                 offset_index);
1391                                 if (!prev->bitmap &&
1392                                     prev->offset + prev->bytes > offset)
1393                                         entry = prev;
1394                         }
1395                 }
1396                 return entry;
1397         }
1398 
1399         if (!prev)
1400                 return NULL;
1401 
1402         /* find last entry before the 'offset' */
1403         entry = prev;
1404         if (entry->offset > offset) {
1405                 n = rb_prev(&entry->offset_index);
1406                 if (n) {
1407                         entry = rb_entry(n, struct btrfs_free_space,
1408                                         offset_index);
1409                         ASSERT(entry->offset <= offset);
1410                 } else {
1411                         if (fuzzy)
1412                                 return entry;
1413                         else
1414                                 return NULL;
1415                 }
1416         }
1417 
1418         if (entry->bitmap) {
1419                 n = rb_prev(&entry->offset_index);
1420                 if (n) {
1421                         prev = rb_entry(n, struct btrfs_free_space,
1422                                         offset_index);
1423                         if (!prev->bitmap &&
1424                             prev->offset + prev->bytes > offset)
1425                                 return prev;
1426                 }
1427                 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1428                         return entry;
1429         } else if (entry->offset + entry->bytes > offset)
1430                 return entry;
1431 
1432         if (!fuzzy)
1433                 return NULL;
1434 
1435         while (1) {
1436                 if (entry->bitmap) {
1437                         if (entry->offset + BITS_PER_BITMAP *
1438                             ctl->unit > offset)
1439                                 break;
1440                 } else {
1441                         if (entry->offset + entry->bytes > offset)
1442                                 break;
1443                 }
1444 
1445                 n = rb_next(&entry->offset_index);
1446                 if (!n)
1447                         return NULL;
1448                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1449         }
1450         return entry;
1451 }
1452 
1453 static inline void
1454 __unlink_free_space(struct btrfs_free_space_ctl *ctl,
1455                     struct btrfs_free_space *info)
1456 {
1457         rb_erase(&info->offset_index, &ctl->free_space_offset);
1458         ctl->free_extents--;
1459 }
1460 
1461 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1462                               struct btrfs_free_space *info)
1463 {
1464         __unlink_free_space(ctl, info);
1465         ctl->free_space -= info->bytes;
1466 }
1467 
1468 static int link_free_space(struct btrfs_free_space_ctl *ctl,
1469                            struct btrfs_free_space *info)
1470 {
1471         int ret = 0;
1472 
1473         ASSERT(info->bytes || info->bitmap);
1474         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1475                                  &info->offset_index, (info->bitmap != NULL));
1476         if (ret)
1477                 return ret;
1478 
1479         ctl->free_space += info->bytes;
1480         ctl->free_extents++;
1481         return ret;
1482 }
1483 
1484 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1485 {
1486         struct btrfs_block_group_cache *block_group = ctl->private;
1487         u64 max_bytes;
1488         u64 bitmap_bytes;
1489         u64 extent_bytes;
1490         u64 size = block_group->key.offset;
1491         u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
1492         int max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1493 
1494         max_bitmaps = max(max_bitmaps, 1);
1495 
1496         ASSERT(ctl->total_bitmaps <= max_bitmaps);
1497 
1498         /*
1499          * The goal is to keep the total amount of memory used per 1gb of space
1500          * at or below 32k, so we need to adjust how much memory we allow to be
1501          * used by extent based free space tracking
1502          */
1503         if (size < 1024 * 1024 * 1024)
1504                 max_bytes = MAX_CACHE_BYTES_PER_GIG;
1505         else
1506                 max_bytes = MAX_CACHE_BYTES_PER_GIG *
1507                         div64_u64(size, 1024 * 1024 * 1024);
1508 
1509         /*
1510          * we want to account for 1 more bitmap than what we have so we can make
1511          * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
1512          * we add more bitmaps.
1513          */
1514         bitmap_bytes = (ctl->total_bitmaps + 1) * PAGE_CACHE_SIZE;
1515 
1516         if (bitmap_bytes >= max_bytes) {
1517                 ctl->extents_thresh = 0;
1518                 return;
1519         }
1520 
1521         /*
1522          * we want the extent entry threshold to always be at most 1/2 the maxw
1523          * bytes we can have, or whatever is less than that.
1524          */
1525         extent_bytes = max_bytes - bitmap_bytes;
1526         extent_bytes = min_t(u64, extent_bytes, div64_u64(max_bytes, 2));
1527 
1528         ctl->extents_thresh =
1529                 div64_u64(extent_bytes, (sizeof(struct btrfs_free_space)));
1530 }
1531 
1532 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1533                                        struct btrfs_free_space *info,
1534                                        u64 offset, u64 bytes)
1535 {
1536         unsigned long start, count;
1537 
1538         start = offset_to_bit(info->offset, ctl->unit, offset);
1539         count = bytes_to_bits(bytes, ctl->unit);
1540         ASSERT(start + count <= BITS_PER_BITMAP);
1541 
1542         bitmap_clear(info->bitmap, start, count);
1543 
1544         info->bytes -= bytes;
1545 }
1546 
1547 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1548                               struct btrfs_free_space *info, u64 offset,
1549                               u64 bytes)
1550 {
1551         __bitmap_clear_bits(ctl, info, offset, bytes);
1552         ctl->free_space -= bytes;
1553 }
1554 
1555 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1556                             struct btrfs_free_space *info, u64 offset,
1557                             u64 bytes)
1558 {
1559         unsigned long start, count;
1560 
1561         start = offset_to_bit(info->offset, ctl->unit, offset);
1562         count = bytes_to_bits(bytes, ctl->unit);
1563         ASSERT(start + count <= BITS_PER_BITMAP);
1564 
1565         bitmap_set(info->bitmap, start, count);
1566 
1567         info->bytes += bytes;
1568         ctl->free_space += bytes;
1569 }
1570 
1571 /*
1572  * If we can not find suitable extent, we will use bytes to record
1573  * the size of the max extent.
1574  */
1575 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1576                          struct btrfs_free_space *bitmap_info, u64 *offset,
1577                          u64 *bytes)
1578 {
1579         unsigned long found_bits = 0;
1580         unsigned long max_bits = 0;
1581         unsigned long bits, i;
1582         unsigned long next_zero;
1583         unsigned long extent_bits;
1584 
1585         i = offset_to_bit(bitmap_info->offset, ctl->unit,
1586                           max_t(u64, *offset, bitmap_info->offset));
1587         bits = bytes_to_bits(*bytes, ctl->unit);
1588 
1589         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
1590                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
1591                                                BITS_PER_BITMAP, i);
1592                 extent_bits = next_zero - i;
1593                 if (extent_bits >= bits) {
1594                         found_bits = extent_bits;
1595                         break;
1596                 } else if (extent_bits > max_bits) {
1597                         max_bits = extent_bits;
1598                 }
1599                 i = next_zero;
1600         }
1601 
1602         if (found_bits) {
1603                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1604                 *bytes = (u64)(found_bits) * ctl->unit;
1605                 return 0;
1606         }
1607 
1608         *bytes = (u64)(max_bits) * ctl->unit;
1609         return -1;
1610 }
1611 
1612 /* Cache the size of the max extent in bytes */
1613 static struct btrfs_free_space *
1614 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
1615                 unsigned long align, u64 *max_extent_size)
1616 {
1617         struct btrfs_free_space *entry;
1618         struct rb_node *node;
1619         u64 tmp;
1620         u64 align_off;
1621         int ret;
1622 
1623         if (!ctl->free_space_offset.rb_node)
1624                 goto out;
1625 
1626         entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1627         if (!entry)
1628                 goto out;
1629 
1630         for (node = &entry->offset_index; node; node = rb_next(node)) {
1631                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1632                 if (entry->bytes < *bytes) {
1633                         if (entry->bytes > *max_extent_size)
1634                                 *max_extent_size = entry->bytes;
1635                         continue;
1636                 }
1637 
1638                 /* make sure the space returned is big enough
1639                  * to match our requested alignment
1640                  */
1641                 if (*bytes >= align) {
1642                         tmp = entry->offset - ctl->start + align - 1;
1643                         do_div(tmp, align);
1644                         tmp = tmp * align + ctl->start;
1645                         align_off = tmp - entry->offset;
1646                 } else {
1647                         align_off = 0;
1648                         tmp = entry->offset;
1649                 }
1650 
1651                 if (entry->bytes < *bytes + align_off) {
1652                         if (entry->bytes > *max_extent_size)
1653                                 *max_extent_size = entry->bytes;
1654                         continue;
1655                 }
1656 
1657                 if (entry->bitmap) {
1658                         u64 size = *bytes;
1659 
1660                         ret = search_bitmap(ctl, entry, &tmp, &size);
1661                         if (!ret) {
1662                                 *offset = tmp;
1663                                 *bytes = size;
1664                                 return entry;
1665                         } else if (size > *max_extent_size) {
1666                                 *max_extent_size = size;
1667                         }
1668                         continue;
1669                 }
1670 
1671                 *offset = tmp;
1672                 *bytes = entry->bytes - align_off;
1673                 return entry;
1674         }
1675 out:
1676         return NULL;
1677 }
1678 
1679 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1680                            struct btrfs_free_space *info, u64 offset)
1681 {
1682         info->offset = offset_to_bitmap(ctl, offset);
1683         info->bytes = 0;
1684         INIT_LIST_HEAD(&info->list);
1685         link_free_space(ctl, info);
1686         ctl->total_bitmaps++;
1687 
1688         ctl->op->recalc_thresholds(ctl);
1689 }
1690 
1691 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1692                         struct btrfs_free_space *bitmap_info)
1693 {
1694         unlink_free_space(ctl, bitmap_info);
1695         kfree(bitmap_info->bitmap);
1696         kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1697         ctl->total_bitmaps--;
1698         ctl->op->recalc_thresholds(ctl);
1699 }
1700 
1701 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1702                               struct btrfs_free_space *bitmap_info,
1703                               u64 *offset, u64 *bytes)
1704 {
1705         u64 end;
1706         u64 search_start, search_bytes;
1707         int ret;
1708 
1709 again:
1710         end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
1711 
1712         /*
1713          * We need to search for bits in this bitmap.  We could only cover some
1714          * of the extent in this bitmap thanks to how we add space, so we need
1715          * to search for as much as it as we can and clear that amount, and then
1716          * go searching for the next bit.
1717          */
1718         search_start = *offset;
1719         search_bytes = ctl->unit;
1720         search_bytes = min(search_bytes, end - search_start + 1);
1721         ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes);
1722         if (ret < 0 || search_start != *offset)
1723                 return -EINVAL;
1724 
1725         /* We may have found more bits than what we need */
1726         search_bytes = min(search_bytes, *bytes);
1727 
1728         /* Cannot clear past the end of the bitmap */
1729         search_bytes = min(search_bytes, end - search_start + 1);
1730 
1731         bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);
1732         *offset += search_bytes;
1733         *bytes -= search_bytes;
1734 
1735         if (*bytes) {
1736                 struct rb_node *next = rb_next(&bitmap_info->offset_index);
1737                 if (!bitmap_info->bytes)
1738                         free_bitmap(ctl, bitmap_info);
1739 
1740                 /*
1741                  * no entry after this bitmap, but we still have bytes to
1742                  * remove, so something has gone wrong.
1743                  */
1744                 if (!next)
1745                         return -EINVAL;
1746 
1747                 bitmap_info = rb_entry(next, struct btrfs_free_space,
1748                                        offset_index);
1749 
1750                 /*
1751                  * if the next entry isn't a bitmap we need to return to let the
1752                  * extent stuff do its work.
1753                  */
1754                 if (!bitmap_info->bitmap)
1755                         return -EAGAIN;
1756 
1757                 /*
1758                  * Ok the next item is a bitmap, but it may not actually hold
1759                  * the information for the rest of this free space stuff, so
1760                  * look for it, and if we don't find it return so we can try
1761                  * everything over again.
1762                  */
1763                 search_start = *offset;
1764                 search_bytes = ctl->unit;
1765                 ret = search_bitmap(ctl, bitmap_info, &search_start,
1766                                     &search_bytes);
1767                 if (ret < 0 || search_start != *offset)
1768                         return -EAGAIN;
1769 
1770                 goto again;
1771         } else if (!bitmap_info->bytes)
1772                 free_bitmap(ctl, bitmap_info);
1773 
1774         return 0;
1775 }
1776 
1777 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
1778                                struct btrfs_free_space *info, u64 offset,
1779                                u64 bytes)
1780 {
1781         u64 bytes_to_set = 0;
1782         u64 end;
1783 
1784         end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
1785 
1786         bytes_to_set = min(end - offset, bytes);
1787 
1788         bitmap_set_bits(ctl, info, offset, bytes_to_set);
1789 
1790         return bytes_to_set;
1791 
1792 }
1793 
1794 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
1795                       struct btrfs_free_space *info)
1796 {
1797         struct btrfs_block_group_cache *block_group = ctl->private;
1798 
1799         /*
1800          * If we are below the extents threshold then we can add this as an
1801          * extent, and don't have to deal with the bitmap
1802          */
1803         if (ctl->free_extents < ctl->extents_thresh) {
1804                 /*
1805                  * If this block group has some small extents we don't want to
1806                  * use up all of our free slots in the cache with them, we want
1807                  * to reserve them to larger extents, however if we have plent
1808                  * of cache left then go ahead an dadd them, no sense in adding
1809                  * the overhead of a bitmap if we don't have to.
1810                  */
1811                 if (info->bytes <= block_group->sectorsize * 4) {
1812                         if (ctl->free_extents * 2 <= ctl->extents_thresh)
1813                                 return false;
1814                 } else {
1815                         return false;
1816                 }
1817         }
1818 
1819         /*
1820          * The original block groups from mkfs can be really small, like 8
1821          * megabytes, so don't bother with a bitmap for those entries.  However
1822          * some block groups can be smaller than what a bitmap would cover but
1823          * are still large enough that they could overflow the 32k memory limit,
1824          * so allow those block groups to still be allowed to have a bitmap
1825          * entry.
1826          */
1827         if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset)
1828                 return false;
1829 
1830         return true;
1831 }
1832 
1833 static struct btrfs_free_space_op free_space_op = {
1834         .recalc_thresholds      = recalculate_thresholds,
1835         .use_bitmap             = use_bitmap,
1836 };
1837 
1838 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
1839                               struct btrfs_free_space *info)
1840 {
1841         struct btrfs_free_space *bitmap_info;
1842         struct btrfs_block_group_cache *block_group = NULL;
1843         int added = 0;
1844         u64 bytes, offset, bytes_added;
1845         int ret;
1846 
1847         bytes = info->bytes;
1848         offset = info->offset;
1849 
1850         if (!ctl->op->use_bitmap(ctl, info))
1851                 return 0;
1852 
1853         if (ctl->op == &free_space_op)
1854                 block_group = ctl->private;
1855 again:
1856         /*
1857          * Since we link bitmaps right into the cluster we need to see if we
1858          * have a cluster here, and if so and it has our bitmap we need to add
1859          * the free space to that bitmap.
1860          */
1861         if (block_group && !list_empty(&block_group->cluster_list)) {
1862                 struct btrfs_free_cluster *cluster;
1863                 struct rb_node *node;
1864                 struct btrfs_free_space *entry;
1865 
1866                 cluster = list_entry(block_group->cluster_list.next,
1867                                      struct btrfs_free_cluster,
1868                                      block_group_list);
1869                 spin_lock(&cluster->lock);
1870                 node = rb_first(&cluster->root);
1871                 if (!node) {
1872                         spin_unlock(&cluster->lock);
1873                         goto no_cluster_bitmap;
1874                 }
1875 
1876                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1877                 if (!entry->bitmap) {
1878                         spin_unlock(&cluster->lock);
1879                         goto no_cluster_bitmap;
1880                 }
1881 
1882                 if (entry->offset == offset_to_bitmap(ctl, offset)) {
1883                         bytes_added = add_bytes_to_bitmap(ctl, entry,
1884                                                           offset, bytes);
1885                         bytes -= bytes_added;
1886                         offset += bytes_added;
1887                 }
1888                 spin_unlock(&cluster->lock);
1889                 if (!bytes) {
1890                         ret = 1;
1891                         goto out;
1892                 }
1893         }
1894 
1895 no_cluster_bitmap:
1896         bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1897                                          1, 0);
1898         if (!bitmap_info) {
1899                 ASSERT(added == 0);
1900                 goto new_bitmap;
1901         }
1902 
1903         bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
1904         bytes -= bytes_added;
1905         offset += bytes_added;
1906         added = 0;
1907 
1908         if (!bytes) {
1909                 ret = 1;
1910                 goto out;
1911         } else
1912                 goto again;
1913 
1914 new_bitmap:
1915         if (info && info->bitmap) {
1916                 add_new_bitmap(ctl, info, offset);
1917                 added = 1;
1918                 info = NULL;
1919                 goto again;
1920         } else {
1921                 spin_unlock(&ctl->tree_lock);
1922 
1923                 /* no pre-allocated info, allocate a new one */
1924                 if (!info) {
1925                         info = kmem_cache_zalloc(btrfs_free_space_cachep,
1926                                                  GFP_NOFS);
1927                         if (!info) {
1928                                 spin_lock(&ctl->tree_lock);
1929                                 ret = -ENOMEM;
1930                                 goto out;
1931                         }
1932                 }
1933 
1934                 /* allocate the bitmap */
1935                 info->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
1936                 spin_lock(&ctl->tree_lock);
1937                 if (!info->bitmap) {
1938                         ret = -ENOMEM;
1939                         goto out;
1940                 }
1941                 goto again;
1942         }
1943 
1944 out:
1945         if (info) {
1946                 if (info->bitmap)
1947                         kfree(info->bitmap);
1948                 kmem_cache_free(btrfs_free_space_cachep, info);
1949         }
1950 
1951         return ret;
1952 }
1953 
1954 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
1955                           struct btrfs_free_space *info, bool update_stat)
1956 {
1957         struct btrfs_free_space *left_info;
1958         struct btrfs_free_space *right_info;
1959         bool merged = false;
1960         u64 offset = info->offset;
1961         u64 bytes = info->bytes;
1962 
1963         /*
1964          * first we want to see if there is free space adjacent to the range we
1965          * are adding, if there is remove that struct and add a new one to
1966          * cover the entire range
1967          */
1968         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
1969         if (right_info && rb_prev(&right_info->offset_index))
1970                 left_info = rb_entry(rb_prev(&right_info->offset_index),
1971                                      struct btrfs_free_space, offset_index);
1972         else
1973                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
1974 
1975         if (right_info && !right_info->bitmap) {
1976                 if (update_stat)
1977                         unlink_free_space(ctl, right_info);
1978                 else
1979                         __unlink_free_space(ctl, right_info);
1980                 info->bytes += right_info->bytes;
1981                 kmem_cache_free(btrfs_free_space_cachep, right_info);
1982                 merged = true;
1983         }
1984 
1985         if (left_info && !left_info->bitmap &&
1986             left_info->offset + left_info->bytes == offset) {
1987                 if (update_stat)
1988                         unlink_free_space(ctl, left_info);
1989                 else
1990                         __unlink_free_space(ctl, left_info);
1991                 info->offset = left_info->offset;
1992                 info->bytes += left_info->bytes;
1993                 kmem_cache_free(btrfs_free_space_cachep, left_info);
1994                 merged = true;
1995         }
1996 
1997         return merged;
1998 }
1999 
2000 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
2001                                      struct btrfs_free_space *info,
2002                                      bool update_stat)
2003 {
2004         struct btrfs_free_space *bitmap;
2005         unsigned long i;
2006         unsigned long j;
2007         const u64 end = info->offset + info->bytes;
2008         const u64 bitmap_offset = offset_to_bitmap(ctl, end);
2009         u64 bytes;
2010 
2011         bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2012         if (!bitmap)
2013                 return false;
2014 
2015         i = offset_to_bit(bitmap->offset, ctl->unit, end);
2016         j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
2017         if (j == i)
2018                 return false;
2019         bytes = (j - i) * ctl->unit;
2020         info->bytes += bytes;
2021 
2022         if (update_stat)
2023                 bitmap_clear_bits(ctl, bitmap, end, bytes);
2024         else
2025                 __bitmap_clear_bits(ctl, bitmap, end, bytes);
2026 
2027         if (!bitmap->bytes)
2028                 free_bitmap(ctl, bitmap);
2029 
2030         return true;
2031 }
2032 
2033 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
2034                                        struct btrfs_free_space *info,
2035                                        bool update_stat)
2036 {
2037         struct btrfs_free_space *bitmap;
2038         u64 bitmap_offset;
2039         unsigned long i;
2040         unsigned long j;
2041         unsigned long prev_j;
2042         u64 bytes;
2043 
2044         bitmap_offset = offset_to_bitmap(ctl, info->offset);
2045         /* If we're on a boundary, try the previous logical bitmap. */
2046         if (bitmap_offset == info->offset) {
2047                 if (info->offset == 0)
2048                         return false;
2049                 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
2050         }
2051 
2052         bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2053         if (!bitmap)
2054                 return false;
2055 
2056         i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
2057         j = 0;
2058         prev_j = (unsigned long)-1;
2059         for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
2060                 if (j > i)
2061                         break;
2062                 prev_j = j;
2063         }
2064         if (prev_j == i)
2065                 return false;
2066 
2067         if (prev_j == (unsigned long)-1)
2068                 bytes = (i + 1) * ctl->unit;
2069         else
2070                 bytes = (i - prev_j) * ctl->unit;
2071 
2072         info->offset -= bytes;
2073         info->bytes += bytes;
2074 
2075         if (update_stat)
2076                 bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2077         else
2078                 __bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2079 
2080         if (!bitmap->bytes)
2081                 free_bitmap(ctl, bitmap);
2082 
2083         return true;
2084 }
2085 
2086 /*
2087  * We prefer always to allocate from extent entries, both for clustered and
2088  * non-clustered allocation requests. So when attempting to add a new extent
2089  * entry, try to see if there's adjacent free space in bitmap entries, and if
2090  * there is, migrate that space from the bitmaps to the extent.
2091  * Like this we get better chances of satisfying space allocation requests
2092  * because we attempt to satisfy them based on a single cache entry, and never
2093  * on 2 or more entries - even if the entries represent a contiguous free space
2094  * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
2095  * ends).
2096  */
2097 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
2098                               struct btrfs_free_space *info,
2099                               bool update_stat)
2100 {
2101         /*
2102          * Only work with disconnected entries, as we can change their offset,
2103          * and must be extent entries.
2104          */
2105         ASSERT(!info->bitmap);
2106         ASSERT(RB_EMPTY_NODE(&info->offset_index));
2107 
2108         if (ctl->total_bitmaps > 0) {
2109                 bool stole_end;
2110                 bool stole_front = false;
2111 
2112                 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
2113                 if (ctl->total_bitmaps > 0)
2114                         stole_front = steal_from_bitmap_to_front(ctl, info,
2115                                                                  update_stat);
2116 
2117                 if (stole_end || stole_front)
2118                         try_merge_free_space(ctl, info, update_stat);
2119         }
2120 }
2121 
2122 int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl,
2123                            u64 offset, u64 bytes)
2124 {
2125         struct btrfs_free_space *info;
2126         int ret = 0;
2127 
2128         info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2129         if (!info)
2130                 return -ENOMEM;
2131 
2132         info->offset = offset;
2133         info->bytes = bytes;
2134         RB_CLEAR_NODE(&info->offset_index);
2135 
2136         spin_lock(&ctl->tree_lock);
2137 
2138         if (try_merge_free_space(ctl, info, true))
2139                 goto link;
2140 
2141         /*
2142          * There was no extent directly to the left or right of this new
2143          * extent then we know we're going to have to allocate a new extent, so
2144          * before we do that see if we need to drop this into a bitmap
2145          */
2146         ret = insert_into_bitmap(ctl, info);
2147         if (ret < 0) {
2148                 goto out;
2149         } else if (ret) {
2150                 ret = 0;
2151                 goto out;
2152         }
2153 link:
2154         /*
2155          * Only steal free space from adjacent bitmaps if we're sure we're not
2156          * going to add the new free space to existing bitmap entries - because
2157          * that would mean unnecessary work that would be reverted. Therefore
2158          * attempt to steal space from bitmaps if we're adding an extent entry.
2159          */
2160         steal_from_bitmap(ctl, info, true);
2161 
2162         ret = link_free_space(ctl, info);
2163         if (ret)
2164                 kmem_cache_free(btrfs_free_space_cachep, info);
2165 out:
2166         spin_unlock(&ctl->tree_lock);
2167 
2168         if (ret) {
2169                 printk(KERN_CRIT "BTRFS: unable to add free space :%d\n", ret);
2170                 ASSERT(ret != -EEXIST);
2171         }
2172 
2173         return ret;
2174 }
2175 
2176 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
2177                             u64 offset, u64 bytes)
2178 {
2179         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2180         struct btrfs_free_space *info;
2181         int ret;
2182         bool re_search = false;
2183 
2184         spin_lock(&ctl->tree_lock);
2185 
2186 again:
2187         ret = 0;
2188         if (!bytes)
2189                 goto out_lock;
2190 
2191         info = tree_search_offset(ctl, offset, 0, 0);
2192         if (!info) {
2193                 /*
2194                  * oops didn't find an extent that matched the space we wanted
2195                  * to remove, look for a bitmap instead
2196                  */
2197                 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2198                                           1, 0);
2199                 if (!info) {
2200                         /*
2201                          * If we found a partial bit of our free space in a
2202                          * bitmap but then couldn't find the other part this may
2203                          * be a problem, so WARN about it.
2204                          */
2205                         WARN_ON(re_search);
2206                         goto out_lock;
2207                 }
2208         }
2209 
2210         re_search = false;
2211         if (!info->bitmap) {
2212                 unlink_free_space(ctl, info);
2213                 if (offset == info->offset) {
2214                         u64 to_free = min(bytes, info->bytes);
2215 
2216                         info->bytes -= to_free;
2217                         info->offset += to_free;
2218                         if (info->bytes) {
2219                                 ret = link_free_space(ctl, info);
2220                                 WARN_ON(ret);
2221                         } else {
2222                                 kmem_cache_free(btrfs_free_space_cachep, info);
2223                         }
2224 
2225                         offset += to_free;
2226                         bytes -= to_free;
2227                         goto again;
2228                 } else {
2229                         u64 old_end = info->bytes + info->offset;
2230 
2231                         info->bytes = offset - info->offset;
2232                         ret = link_free_space(ctl, info);
2233                         WARN_ON(ret);
2234                         if (ret)
2235                                 goto out_lock;
2236 
2237                         /* Not enough bytes in this entry to satisfy us */
2238                         if (old_end < offset + bytes) {
2239                                 bytes -= old_end - offset;
2240                                 offset = old_end;
2241                                 goto again;
2242                         } else if (old_end == offset + bytes) {
2243                                 /* all done */
2244                                 goto out_lock;
2245                         }
2246                         spin_unlock(&ctl->tree_lock);
2247 
2248                         ret = btrfs_add_free_space(block_group, offset + bytes,
2249                                                    old_end - (offset + bytes));
2250                         WARN_ON(ret);
2251                         goto out;
2252                 }
2253         }
2254 
2255         ret = remove_from_bitmap(ctl, info, &offset, &bytes);
2256         if (ret == -EAGAIN) {
2257                 re_search = true;
2258                 goto again;
2259         }
2260 out_lock:
2261         spin_unlock(&ctl->tree_lock);
2262 out:
2263         return ret;
2264 }
2265 
2266 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
2267                            u64 bytes)
2268 {
2269         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2270         struct btrfs_free_space *info;
2271         struct rb_node *n;
2272         int count = 0;
2273 
2274         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
2275                 info = rb_entry(n, struct btrfs_free_space, offset_index);
2276                 if (info->bytes >= bytes && !block_group->ro)
2277                         count++;
2278                 btrfs_crit(block_group->fs_info,
2279                            "entry offset %llu, bytes %llu, bitmap %s",
2280                            info->offset, info->bytes,
2281                        (info->bitmap) ? "yes" : "no");
2282         }
2283         btrfs_info(block_group->fs_info, "block group has cluster?: %s",
2284                list_empty(&block_group->cluster_list) ? "no" : "yes");
2285         btrfs_info(block_group->fs_info,
2286                    "%d blocks of free space at or bigger than bytes is", count);
2287 }
2288 
2289 void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
2290 {
2291         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2292 
2293         spin_lock_init(&ctl->tree_lock);
2294         ctl->unit = block_group->sectorsize;
2295         ctl->start = block_group->key.objectid;
2296         ctl->private = block_group;
2297         ctl->op = &free_space_op;
2298 
2299         /*
2300          * we only want to have 32k of ram per block group for keeping
2301          * track of free space, and if we pass 1/2 of that we want to
2302          * start converting things over to using bitmaps
2303          */
2304         ctl->extents_thresh = ((1024 * 32) / 2) /
2305                                 sizeof(struct btrfs_free_space);
2306 }
2307 
2308 /*
2309  * for a given cluster, put all of its extents back into the free
2310  * space cache.  If the block group passed doesn't match the block group
2311  * pointed to by the cluster, someone else raced in and freed the
2312  * cluster already.  In that case, we just return without changing anything
2313  */
2314 static int
2315 __btrfs_return_cluster_to_free_space(
2316                              struct btrfs_block_group_cache *block_group,
2317                              struct btrfs_free_cluster *cluster)
2318 {
2319         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2320         struct btrfs_free_space *entry;
2321         struct rb_node *node;
2322 
2323         spin_lock(&cluster->lock);
2324         if (cluster->block_group != block_group)
2325                 goto out;
2326 
2327         cluster->block_group = NULL;
2328         cluster->window_start = 0;
2329         list_del_init(&cluster->block_group_list);
2330 
2331         node = rb_first(&cluster->root);
2332         while (node) {
2333                 bool bitmap;
2334 
2335                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2336                 node = rb_next(&entry->offset_index);
2337                 rb_erase(&entry->offset_index, &cluster->root);
2338                 RB_CLEAR_NODE(&entry->offset_index);
2339 
2340                 bitmap = (entry->bitmap != NULL);
2341                 if (!bitmap) {
2342                         try_merge_free_space(ctl, entry, false);
2343                         steal_from_bitmap(ctl, entry, false);
2344                 }
2345                 tree_insert_offset(&ctl->free_space_offset,
2346                                    entry->offset, &entry->offset_index, bitmap);
2347         }
2348         cluster->root = RB_ROOT;
2349 
2350 out:
2351         spin_unlock(&cluster->lock);
2352         btrfs_put_block_group(block_group);
2353         return 0;
2354 }
2355 
2356 static void __btrfs_remove_free_space_cache_locked(
2357                                 struct btrfs_free_space_ctl *ctl)
2358 {
2359         struct btrfs_free_space *info;
2360         struct rb_node *node;
2361 
2362         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
2363                 info = rb_entry(node, struct btrfs_free_space, offset_index);
2364                 if (!info->bitmap) {
2365                         unlink_free_space(ctl, info);
2366                         kmem_cache_free(btrfs_free_space_cachep, info);
2367                 } else {
2368                         free_bitmap(ctl, info);
2369                 }
2370                 if (need_resched()) {
2371                         spin_unlock(&ctl->tree_lock);
2372                         cond_resched();
2373                         spin_lock(&ctl->tree_lock);
2374                 }
2375         }
2376 }
2377 
2378 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
2379 {
2380         spin_lock(&ctl->tree_lock);
2381         __btrfs_remove_free_space_cache_locked(ctl);
2382         spin_unlock(&ctl->tree_lock);
2383 }
2384 
2385 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
2386 {
2387         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2388         struct btrfs_free_cluster *cluster;
2389         struct list_head *head;
2390 
2391         spin_lock(&ctl->tree_lock);
2392         while ((head = block_group->cluster_list.next) !=
2393                &block_group->cluster_list) {
2394                 cluster = list_entry(head, struct btrfs_free_cluster,
2395                                      block_group_list);
2396 
2397                 WARN_ON(cluster->block_group != block_group);
2398                 __btrfs_return_cluster_to_free_space(block_group, cluster);
2399                 if (need_resched()) {
2400                         spin_unlock(&ctl->tree_lock);
2401                         cond_resched();
2402                         spin_lock(&ctl->tree_lock);
2403                 }
2404         }
2405         __btrfs_remove_free_space_cache_locked(ctl);
2406         spin_unlock(&ctl->tree_lock);
2407 
2408 }
2409 
2410 u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
2411                                u64 offset, u64 bytes, u64 empty_size,
2412                                u64 *max_extent_size)
2413 {
2414         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2415         struct btrfs_free_space *entry = NULL;
2416         u64 bytes_search = bytes + empty_size;
2417         u64 ret = 0;
2418         u64 align_gap = 0;
2419         u64 align_gap_len = 0;
2420 
2421         spin_lock(&ctl->tree_lock);
2422         entry = find_free_space(ctl, &offset, &bytes_search,
2423                                 block_group->full_stripe_len, max_extent_size);
2424         if (!entry)
2425                 goto out;
2426 
2427         ret = offset;
2428         if (entry->bitmap) {
2429                 bitmap_clear_bits(ctl, entry, offset, bytes);
2430                 if (!entry->bytes)
2431                         free_bitmap(ctl, entry);
2432         } else {
2433                 unlink_free_space(ctl, entry);
2434                 align_gap_len = offset - entry->offset;
2435                 align_gap = entry->offset;
2436 
2437                 entry->offset = offset + bytes;
2438                 WARN_ON(entry->bytes < bytes + align_gap_len);
2439 
2440                 entry->bytes -= bytes + align_gap_len;
2441                 if (!entry->bytes)
2442                         kmem_cache_free(btrfs_free_space_cachep, entry);
2443                 else
2444                         link_free_space(ctl, entry);
2445         }
2446 out:
2447         spin_unlock(&ctl->tree_lock);
2448 
2449         if (align_gap_len)
2450                 __btrfs_add_free_space(ctl, align_gap, align_gap_len);
2451         return ret;
2452 }
2453 
2454 /*
2455  * given a cluster, put all of its extents back into the free space
2456  * cache.  If a block group is passed, this function will only free
2457  * a cluster that belongs to the passed block group.
2458  *
2459  * Otherwise, it'll get a reference on the block group pointed to by the
2460  * cluster and remove the cluster from it.
2461  */
2462 int btrfs_return_cluster_to_free_space(
2463                                struct btrfs_block_group_cache *block_group,
2464                                struct btrfs_free_cluster *cluster)
2465 {
2466         struct btrfs_free_space_ctl *ctl;
2467         int ret;
2468 
2469         /* first, get a safe pointer to the block group */
2470         spin_lock(&cluster->lock);
2471         if (!block_group) {
2472                 block_group = cluster->block_group;
2473                 if (!block_group) {
2474                         spin_unlock(&cluster->lock);
2475                         return 0;
2476                 }
2477         } else if (cluster->block_group != block_group) {
2478                 /* someone else has already freed it don't redo their work */
2479                 spin_unlock(&cluster->lock);
2480                 return 0;
2481         }
2482         atomic_inc(&block_group->count);
2483         spin_unlock(&cluster->lock);
2484 
2485         ctl = block_group->free_space_ctl;
2486 
2487         /* now return any extents the cluster had on it */
2488         spin_lock(&ctl->tree_lock);
2489         ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
2490         spin_unlock(&ctl->tree_lock);
2491 
2492         /* finally drop our ref */
2493         btrfs_put_block_group(block_group);
2494         return ret;
2495 }
2496 
2497 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
2498                                    struct btrfs_free_cluster *cluster,
2499                                    struct btrfs_free_space *entry,
2500                                    u64 bytes, u64 min_start,
2501                                    u64 *max_extent_size)
2502 {
2503         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2504         int err;
2505         u64 search_start = cluster->window_start;
2506         u64 search_bytes = bytes;
2507         u64 ret = 0;
2508 
2509         search_start = min_start;
2510         search_bytes = bytes;
2511 
2512         err = search_bitmap(ctl, entry, &search_start, &search_bytes);
2513         if (err) {
2514                 if (search_bytes > *max_extent_size)
2515                         *max_extent_size = search_bytes;
2516                 return 0;
2517         }
2518 
2519         ret = search_start;
2520         __bitmap_clear_bits(ctl, entry, ret, bytes);
2521 
2522         return ret;
2523 }
2524 
2525 /*
2526  * given a cluster, try to allocate 'bytes' from it, returns 0
2527  * if it couldn't find anything suitably large, or a logical disk offset
2528  * if things worked out
2529  */
2530 u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
2531                              struct btrfs_free_cluster *cluster, u64 bytes,
2532                              u64 min_start, u64 *max_extent_size)
2533 {
2534         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2535         struct btrfs_free_space *entry = NULL;
2536         struct rb_node *node;
2537         u64 ret = 0;
2538 
2539         spin_lock(&cluster->lock);
2540         if (bytes > cluster->max_size)
2541                 goto out;
2542 
2543         if (cluster->block_group != block_group)
2544                 goto out;
2545 
2546         node = rb_first(&cluster->root);
2547         if (!node)
2548                 goto out;
2549 
2550         entry = rb_entry(node, struct btrfs_free_space, offset_index);
2551         while (1) {
2552                 if (entry->bytes < bytes && entry->bytes > *max_extent_size)
2553                         *max_extent_size = entry->bytes;
2554 
2555                 if (entry->bytes < bytes ||
2556                     (!entry->bitmap && entry->offset < min_start)) {
2557                         node = rb_next(&entry->offset_index);
2558                         if (!node)
2559                                 break;
2560                         entry = rb_entry(node, struct btrfs_free_space,
2561                                          offset_index);
2562                         continue;
2563                 }
2564 
2565                 if (entry->bitmap) {
2566                         ret = btrfs_alloc_from_bitmap(block_group,
2567                                                       cluster, entry, bytes,
2568                                                       cluster->window_start,
2569                                                       max_extent_size);
2570                         if (ret == 0) {
2571                                 node = rb_next(&entry->offset_index);
2572                                 if (!node)
2573                                         break;
2574                                 entry = rb_entry(node, struct btrfs_free_space,
2575                                                  offset_index);
2576                                 continue;
2577                         }
2578                         cluster->window_start += bytes;
2579                 } else {
2580                         ret = entry->offset;
2581 
2582                         entry->offset += bytes;
2583                         entry->bytes -= bytes;
2584                 }
2585 
2586                 if (entry->bytes == 0)
2587                         rb_erase(&entry->offset_index, &cluster->root);
2588                 break;
2589         }
2590 out:
2591         spin_unlock(&cluster->lock);
2592 
2593         if (!ret)
2594                 return 0;
2595 
2596         spin_lock(&ctl->tree_lock);
2597 
2598         ctl->free_space -= bytes;
2599         if (entry->bytes == 0) {
2600                 ctl->free_extents--;
2601                 if (entry->bitmap) {
2602                         kfree(entry->bitmap);
2603                         ctl->total_bitmaps--;
2604                         ctl->op->recalc_thresholds(ctl);
2605                 }
2606                 kmem_cache_free(btrfs_free_space_cachep, entry);
2607         }
2608 
2609         spin_unlock(&ctl->tree_lock);
2610 
2611         return ret;
2612 }
2613 
2614 static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
2615                                 struct btrfs_free_space *entry,
2616                                 struct btrfs_free_cluster *cluster,
2617                                 u64 offset, u64 bytes,
2618                                 u64 cont1_bytes, u64 min_bytes)
2619 {
2620         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2621         unsigned long next_zero;
2622         unsigned long i;
2623         unsigned long want_bits;
2624         unsigned long min_bits;
2625         unsigned long found_bits;
2626         unsigned long start = 0;
2627         unsigned long total_found = 0;
2628         int ret;
2629 
2630         i = offset_to_bit(entry->offset, ctl->unit,
2631                           max_t(u64, offset, entry->offset));
2632         want_bits = bytes_to_bits(bytes, ctl->unit);
2633         min_bits = bytes_to_bits(min_bytes, ctl->unit);
2634 
2635 again:
2636         found_bits = 0;
2637         for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2638                 next_zero = find_next_zero_bit(entry->bitmap,
2639                                                BITS_PER_BITMAP, i);
2640                 if (next_zero - i >= min_bits) {
2641                         found_bits = next_zero - i;
2642                         break;
2643                 }
2644                 i = next_zero;
2645         }
2646 
2647         if (!found_bits)
2648                 return -ENOSPC;
2649 
2650         if (!total_found) {
2651                 start = i;
2652                 cluster->max_size = 0;
2653         }
2654 
2655         total_found += found_bits;
2656 
2657         if (cluster->max_size < found_bits * ctl->unit)
2658                 cluster->max_size = found_bits * ctl->unit;
2659 
2660         if (total_found < want_bits || cluster->max_size < cont1_bytes) {
2661                 i = next_zero + 1;
2662                 goto again;
2663         }
2664 
2665         cluster->window_start = start * ctl->unit + entry->offset;
2666         rb_erase(&entry->offset_index, &ctl->free_space_offset);
2667         ret = tree_insert_offset(&cluster->root, entry->offset,
2668                                  &entry->offset_index, 1);
2669         ASSERT(!ret); /* -EEXIST; Logic error */
2670 
2671         trace_btrfs_setup_cluster(block_group, cluster,
2672                                   total_found * ctl->unit, 1);
2673         return 0;
2674 }
2675 
2676 /*
2677  * This searches the block group for just extents to fill the cluster with.
2678  * Try to find a cluster with at least bytes total bytes, at least one
2679  * extent of cont1_bytes, and other clusters of at least min_bytes.
2680  */
2681 static noinline int
2682 setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
2683                         struct btrfs_free_cluster *cluster,
2684                         struct list_head *bitmaps, u64 offset, u64 bytes,
2685                         u64 cont1_bytes, u64 min_bytes)
2686 {
2687         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2688         struct btrfs_free_space *first = NULL;
2689         struct btrfs_free_space *entry = NULL;
2690         struct btrfs_free_space *last;
2691         struct rb_node *node;
2692         u64 window_free;
2693         u64 max_extent;
2694         u64 total_size = 0;
2695 
2696         entry = tree_search_offset(ctl, offset, 0, 1);
2697         if (!entry)
2698                 return -ENOSPC;
2699 
2700         /*
2701          * We don't want bitmaps, so just move along until we find a normal
2702          * extent entry.
2703          */
2704         while (entry->bitmap || entry->bytes < min_bytes) {
2705                 if (entry->bitmap && list_empty(&entry->list))
2706                         list_add_tail(&entry->list, bitmaps);
2707                 node = rb_next(&entry->offset_index);
2708                 if (!node)
2709                         return -ENOSPC;
2710                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2711         }
2712 
2713         window_free = entry->bytes;
2714         max_extent = entry->bytes;
2715         first = entry;
2716         last = entry;
2717 
2718         for (node = rb_next(&entry->offset_index); node;
2719              node = rb_next(&entry->offset_index)) {
2720                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2721 
2722                 if (entry->bitmap) {
2723                         if (list_empty(&entry->list))
2724                                 list_add_tail(&entry->list, bitmaps);
2725                         continue;
2726                 }
2727 
2728                 if (entry->bytes < min_bytes)
2729                         continue;
2730 
2731                 last = entry;
2732                 window_free += entry->bytes;
2733                 if (entry->bytes > max_extent)
2734                         max_extent = entry->bytes;
2735         }
2736 
2737         if (window_free < bytes || max_extent < cont1_bytes)
2738                 return -ENOSPC;
2739 
2740         cluster->window_start = first->offset;
2741 
2742         node = &first->offset_index;
2743 
2744         /*
2745          * now we've found our entries, pull them out of the free space
2746          * cache and put them into the cluster rbtree
2747          */
2748         do {
2749                 int ret;
2750 
2751                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2752                 node = rb_next(&entry->offset_index);
2753                 if (entry->bitmap || entry->bytes < min_bytes)
2754                         continue;
2755 
2756                 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2757                 ret = tree_insert_offset(&cluster->root, entry->offset,
2758                                          &entry->offset_index, 0);
2759                 total_size += entry->bytes;
2760                 ASSERT(!ret); /* -EEXIST; Logic error */
2761         } while (node && entry != last);
2762 
2763         cluster->max_size = max_extent;
2764         trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
2765         return 0;
2766 }
2767 
2768 /*
2769  * This specifically looks for bitmaps that may work in the cluster, we assume
2770  * that we have already failed to find extents that will work.
2771  */
2772 static noinline int
2773 setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
2774                      struct btrfs_free_cluster *cluster,
2775                      struct list_head *bitmaps, u64 offset, u64 bytes,
2776                      u64 cont1_bytes, u64 min_bytes)
2777 {
2778         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2779         struct btrfs_free_space *entry;
2780         int ret = -ENOSPC;
2781         u64 bitmap_offset = offset_to_bitmap(ctl, offset);
2782 
2783         if (ctl->total_bitmaps == 0)
2784                 return -ENOSPC;
2785 
2786         /*
2787          * The bitmap that covers offset won't be in the list unless offset
2788          * is just its start offset.
2789          */
2790         entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
2791         if (entry->offset != bitmap_offset) {
2792                 entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
2793                 if (entry && list_empty(&entry->list))
2794                         list_add(&entry->list, bitmaps);
2795         }
2796 
2797         list_for_each_entry(entry, bitmaps, list) {
2798                 if (entry->bytes < bytes)
2799                         continue;
2800                 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2801                                            bytes, cont1_bytes, min_bytes);
2802                 if (!ret)
2803                         return 0;
2804         }
2805 
2806         /*
2807          * The bitmaps list has all the bitmaps that record free space
2808          * starting after offset, so no more search is required.
2809          */
2810         return -ENOSPC;
2811 }
2812 
2813 /*
2814  * here we try to find a cluster of blocks in a block group.  The goal
2815  * is to find at least bytes+empty_size.
2816  * We might not find them all in one contiguous area.
2817  *
2818  * returns zero and sets up cluster if things worked out, otherwise
2819  * it returns -enospc
2820  */
2821 int btrfs_find_space_cluster(struct btrfs_root *root,
2822                              struct btrfs_block_group_cache *block_group,
2823                              struct btrfs_free_cluster *cluster,
2824                              u64 offset, u64 bytes, u64 empty_size)
2825 {
2826         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2827         struct btrfs_free_space *entry, *tmp;
2828         LIST_HEAD(bitmaps);
2829         u64 min_bytes;
2830         u64 cont1_bytes;
2831         int ret;
2832 
2833         /*
2834          * Choose the minimum extent size we'll require for this
2835          * cluster.  For SSD_SPREAD, don't allow any fragmentation.
2836          * For metadata, allow allocates with smaller extents.  For
2837          * data, keep it dense.
2838          */
2839         if (btrfs_test_opt(root, SSD_SPREAD)) {
2840                 cont1_bytes = min_bytes = bytes + empty_size;
2841         } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
2842                 cont1_bytes = bytes;
2843                 min_bytes = block_group->sectorsize;
2844         } else {
2845                 cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
2846                 min_bytes = block_group->sectorsize;
2847         }
2848 
2849         spin_lock(&ctl->tree_lock);
2850 
2851         /*
2852          * If we know we don't have enough space to make a cluster don't even
2853          * bother doing all the work to try and find one.
2854          */
2855         if (ctl->free_space < bytes) {
2856                 spin_unlock(&ctl->tree_lock);
2857                 return -ENOSPC;
2858         }
2859 
2860         spin_lock(&cluster->lock);
2861 
2862         /* someone already found a cluster, hooray */
2863         if (cluster->block_group) {
2864                 ret = 0;
2865                 goto out;
2866         }
2867 
2868         trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
2869                                  min_bytes);
2870 
2871         INIT_LIST_HEAD(&bitmaps);
2872         ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
2873                                       bytes + empty_size,
2874                                       cont1_bytes, min_bytes);
2875         if (ret)
2876                 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
2877                                            offset, bytes + empty_size,
2878                                            cont1_bytes, min_bytes);
2879 
2880         /* Clear our temporary list */
2881         list_for_each_entry_safe(entry, tmp, &bitmaps, list)
2882                 list_del_init(&entry->list);
2883 
2884         if (!ret) {
2885                 atomic_inc(&block_group->count);
2886                 list_add_tail(&cluster->block_group_list,
2887                               &block_group->cluster_list);
2888                 cluster->block_group = block_group;
2889         } else {
2890                 trace_btrfs_failed_cluster_setup(block_group);
2891         }
2892 out:
2893         spin_unlock(&cluster->lock);
2894         spin_unlock(&ctl->tree_lock);
2895 
2896         return ret;
2897 }
2898 
2899 /*
2900  * simple code to zero out a cluster
2901  */
2902 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
2903 {
2904         spin_lock_init(&cluster->lock);
2905         spin_lock_init(&cluster->refill_lock);
2906         cluster->root = RB_ROOT;
2907         cluster->max_size = 0;
2908         INIT_LIST_HEAD(&cluster->block_group_list);
2909         cluster->block_group = NULL;
2910 }
2911 
2912 static int do_trimming(struct btrfs_block_group_cache *block_group,
2913                        u64 *total_trimmed, u64 start, u64 bytes,
2914                        u64 reserved_start, u64 reserved_bytes)
2915 {
2916         struct btrfs_space_info *space_info = block_group->space_info;
2917         struct btrfs_fs_info *fs_info = block_group->fs_info;
2918         int ret;
2919         int update = 0;
2920         u64 trimmed = 0;
2921 
2922         spin_lock(&space_info->lock);
2923         spin_lock(&block_group->lock);
2924         if (!block_group->ro) {
2925                 block_group->reserved += reserved_bytes;
2926                 space_info->bytes_reserved += reserved_bytes;
2927                 update = 1;
2928         }
2929         spin_unlock(&block_group->lock);
2930         spin_unlock(&space_info->lock);
2931 
2932         ret = btrfs_error_discard_extent(fs_info->extent_root,
2933                                          start, bytes, &trimmed);
2934         if (!ret)
2935                 *total_trimmed += trimmed;
2936 
2937         btrfs_add_free_space(block_group, reserved_start, reserved_bytes);
2938 
2939         if (update) {
2940                 spin_lock(&space_info->lock);
2941                 spin_lock(&block_group->lock);
2942                 if (block_group->ro)
2943                         space_info->bytes_readonly += reserved_bytes;
2944                 block_group->reserved -= reserved_bytes;
2945                 space_info->bytes_reserved -= reserved_bytes;
2946                 spin_unlock(&space_info->lock);
2947                 spin_unlock(&block_group->lock);
2948         }
2949 
2950         return ret;
2951 }
2952 
2953 static int trim_no_bitmap(struct btrfs_block_group_cache *block_group,
2954                           u64 *total_trimmed, u64 start, u64 end, u64 minlen)
2955 {
2956         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2957         struct btrfs_free_space *entry;
2958         struct rb_node *node;
2959         int ret = 0;
2960         u64 extent_start;
2961         u64 extent_bytes;
2962         u64 bytes;
2963 
2964         while (start < end) {
2965                 spin_lock(&ctl->tree_lock);
2966 
2967                 if (ctl->free_space < minlen) {
2968                         spin_unlock(&ctl->tree_lock);
2969                         break;
2970                 }
2971 
2972                 entry = tree_search_offset(ctl, start, 0, 1);
2973                 if (!entry) {
2974                         spin_unlock(&ctl->tree_lock);
2975                         break;
2976                 }
2977 
2978                 /* skip bitmaps */
2979                 while (entry->bitmap) {
2980                         node = rb_next(&entry->offset_index);
2981                         if (!node) {
2982                                 spin_unlock(&ctl->tree_lock);
2983                                 goto out;
2984                         }
2985                         entry = rb_entry(node, struct btrfs_free_space,
2986                                          offset_index);
2987                 }
2988 
2989                 if (entry->offset >= end) {
2990                         spin_unlock(&ctl->tree_lock);
2991                         break;
2992                 }
2993 
2994                 extent_start = entry->offset;
2995                 extent_bytes = entry->bytes;
2996                 start = max(start, extent_start);
2997                 bytes = min(extent_start + extent_bytes, end) - start;
2998                 if (bytes < minlen) {
2999                         spin_unlock(&ctl->tree_lock);
3000                         goto next;
3001                 }
3002 
3003                 unlink_free_space(ctl, entry);
3004                 kmem_cache_free(btrfs_free_space_cachep, entry);
3005 
3006                 spin_unlock(&ctl->tree_lock);
3007 
3008                 ret = do_trimming(block_group, total_trimmed, start, bytes,
3009                                   extent_start, extent_bytes);
3010                 if (ret)
3011                         break;
3012 next:
3013                 start += bytes;
3014 
3015                 if (fatal_signal_pending(current)) {
3016                         ret = -ERESTARTSYS;
3017                         break;
3018                 }
3019 
3020                 cond_resched();
3021         }
3022 out:
3023         return ret;
3024 }
3025 
3026 static int trim_bitmaps(struct btrfs_block_group_cache *block_group,
3027                         u64 *total_trimmed, u64 start, u64 end, u64 minlen)
3028 {
3029         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3030         struct btrfs_free_space *entry;
3031         int ret = 0;
3032         int ret2;
3033         u64 bytes;
3034         u64 offset = offset_to_bitmap(ctl, start);
3035 
3036         while (offset < end) {
3037                 bool next_bitmap = false;
3038 
3039                 spin_lock(&ctl->tree_lock);
3040 
3041                 if (ctl->free_space < minlen) {
3042                         spin_unlock(&ctl->tree_lock);
3043                         break;
3044                 }
3045 
3046                 entry = tree_search_offset(ctl, offset, 1, 0);
3047                 if (!entry) {
3048                         spin_unlock(&ctl->tree_lock);
3049                         next_bitmap = true;
3050                         goto next;
3051                 }
3052 
3053                 bytes = minlen;
3054                 ret2 = search_bitmap(ctl, entry, &start, &bytes);
3055                 if (ret2 || start >= end) {
3056                         spin_unlock(&ctl->tree_lock);
3057                         next_bitmap = true;
3058                         goto next;
3059                 }
3060 
3061                 bytes = min(bytes, end - start);
3062                 if (bytes < minlen) {
3063                         spin_unlock(&ctl->tree_lock);
3064                         goto next;
3065                 }
3066 
3067                 bitmap_clear_bits(ctl, entry, start, bytes);
3068                 if (entry->bytes == 0)
3069                         free_bitmap(ctl, entry);
3070 
3071                 spin_unlock(&ctl->tree_lock);
3072 
3073                 ret = do_trimming(block_group, total_trimmed, start, bytes,
3074                                   start, bytes);
3075                 if (ret)
3076                         break;
3077 next:
3078                 if (next_bitmap) {
3079                         offset += BITS_PER_BITMAP * ctl->unit;
3080                 } else {
3081                         start += bytes;
3082                         if (start >= offset + BITS_PER_BITMAP * ctl->unit)
3083                                 offset += BITS_PER_BITMAP * ctl->unit;
3084                 }
3085 
3086                 if (fatal_signal_pending(current)) {
3087                         ret = -ERESTARTSYS;
3088                         break;
3089                 }
3090 
3091                 cond_resched();
3092         }
3093 
3094         return ret;
3095 }
3096 
3097 int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
3098                            u64 *trimmed, u64 start, u64 end, u64 minlen)
3099 {
3100         int ret;
3101 
3102         *trimmed = 0;
3103 
3104         ret = trim_no_bitmap(block_group, trimmed, start, end, minlen);
3105         if (ret)
3106                 return ret;
3107 
3108         ret = trim_bitmaps(block_group, trimmed, start, end, minlen);
3109 
3110         return ret;
3111 }
3112 
3113 /*
3114  * Find the left-most item in the cache tree, and then return the
3115  * smallest inode number in the item.
3116  *
3117  * Note: the returned inode number may not be the smallest one in
3118  * the tree, if the left-most item is a bitmap.
3119  */
3120 u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
3121 {
3122         struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
3123         struct btrfs_free_space *entry = NULL;
3124         u64 ino = 0;
3125 
3126         spin_lock(&ctl->tree_lock);
3127 
3128         if (RB_EMPTY_ROOT(&ctl->free_space_offset))
3129                 goto out;
3130 
3131         entry = rb_entry(rb_first(&ctl->free_space_offset),
3132                          struct btrfs_free_space, offset_index);
3133 
3134         if (!entry->bitmap) {
3135                 ino = entry->offset;
3136 
3137                 unlink_free_space(ctl, entry);
3138                 entry->offset++;
3139                 entry->bytes--;
3140                 if (!entry->bytes)
3141                         kmem_cache_free(btrfs_free_space_cachep, entry);
3142                 else
3143                         link_free_space(ctl, entry);
3144         } else {
3145                 u64 offset = 0;
3146                 u64 count = 1;
3147                 int ret;
3148 
3149                 ret = search_bitmap(ctl, entry, &offset, &count);
3150                 /* Logic error; Should be empty if it can't find anything */
3151                 ASSERT(!ret);
3152 
3153                 ino = offset;
3154                 bitmap_clear_bits(ctl, entry, offset, 1);
3155                 if (entry->bytes == 0)
3156                         free_bitmap(ctl, entry);
3157         }
3158 out:
3159         spin_unlock(&ctl->tree_lock);
3160 
3161         return ino;
3162 }
3163 
3164 struct inode *lookup_free_ino_inode(struct btrfs_root *root,
3165                                     struct btrfs_path *path)
3166 {
3167         struct inode *inode = NULL;
3168 
3169         spin_lock(&root->ino_cache_lock);
3170         if (root->ino_cache_inode)
3171                 inode = igrab(root->ino_cache_inode);
3172         spin_unlock(&root->ino_cache_lock);
3173         if (inode)
3174                 return inode;
3175 
3176         inode = __lookup_free_space_inode(root, path, 0);
3177         if (IS_ERR(inode))
3178                 return inode;
3179 
3180         spin_lock(&root->ino_cache_lock);
3181         if (!btrfs_fs_closing(root->fs_info))
3182                 root->ino_cache_inode = igrab(inode);
3183         spin_unlock(&root->ino_cache_lock);
3184 
3185         return inode;
3186 }
3187 
3188 int create_free_ino_inode(struct btrfs_root *root,
3189                           struct btrfs_trans_handle *trans,
3190                           struct btrfs_path *path)
3191 {
3192         return __create_free_space_inode(root, trans, path,
3193                                          BTRFS_FREE_INO_OBJECTID, 0);
3194 }
3195 
3196 int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
3197 {
3198         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
3199         struct btrfs_path *path;
3200         struct inode *inode;
3201         int ret = 0;
3202         u64 root_gen = btrfs_root_generation(&root->root_item);
3203 
3204         if (!btrfs_test_opt(root, INODE_MAP_CACHE))
3205                 return 0;
3206 
3207         /*
3208          * If we're unmounting then just return, since this does a search on the
3209          * normal root and not the commit root and we could deadlock.
3210          */
3211         if (btrfs_fs_closing(fs_info))
3212                 return 0;
3213 
3214         path = btrfs_alloc_path();
3215         if (!path)
3216                 return 0;
3217 
3218         inode = lookup_free_ino_inode(root, path);
3219         if (IS_ERR(inode))
3220                 goto out;
3221 
3222         if (root_gen != BTRFS_I(inode)->generation)
3223                 goto out_put;
3224 
3225         ret = __load_free_space_cache(root, inode, ctl, path, 0);
3226 
3227         if (ret < 0)
3228                 btrfs_err(fs_info,
3229                         "failed to load free ino cache for root %llu",
3230                         root->root_key.objectid);
3231 out_put:
3232         iput(inode);
3233 out:
3234         btrfs_free_path(path);
3235         return ret;
3236 }
3237 
3238 int btrfs_write_out_ino_cache(struct btrfs_root *root,
3239                               struct btrfs_trans_handle *trans,
3240                               struct btrfs_path *path,
3241                               struct inode *inode)
3242 {
3243         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
3244         int ret;
3245 
3246         if (!btrfs_test_opt(root, INODE_MAP_CACHE))
3247                 return 0;
3248 
3249         ret = __btrfs_write_out_cache(root, inode, ctl, NULL, trans, path, 0);
3250         if (ret) {
3251                 btrfs_delalloc_release_metadata(inode, inode->i_size);
3252 #ifdef DEBUG
3253                 btrfs_err(root->fs_info,
3254                         "failed to write free ino cache for root %llu",
3255                         root->root_key.objectid);
3256 #endif
3257         }
3258 
3259         return ret;
3260 }
3261 
3262 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
3263 /*
3264  * Use this if you need to make a bitmap or extent entry specifically, it
3265  * doesn't do any of the merging that add_free_space does, this acts a lot like
3266  * how the free space cache loading stuff works, so you can get really weird
3267  * configurations.
3268  */
3269 int test_add_free_space_entry(struct btrfs_block_group_cache *cache,
3270                               u64 offset, u64 bytes, bool bitmap)
3271 {
3272         struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3273         struct btrfs_free_space *info = NULL, *bitmap_info;
3274         void *map = NULL;
3275         u64 bytes_added;
3276         int ret;
3277 
3278 again:
3279         if (!info) {
3280                 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
3281                 if (!info)
3282                         return -ENOMEM;
3283         }
3284 
3285         if (!bitmap) {
3286                 spin_lock(&ctl->tree_lock);
3287                 info->offset = offset;
3288                 info->bytes = bytes;
3289                 ret = link_free_space(ctl, info);
3290                 spin_unlock(&ctl->tree_lock);
3291                 if (ret)
3292                         kmem_cache_free(btrfs_free_space_cachep, info);
3293                 return ret;
3294         }
3295 
3296         if (!map) {
3297                 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3298                 if (!map) {
3299                         kmem_cache_free(btrfs_free_space_cachep, info);
3300                         return -ENOMEM;
3301                 }
3302         }
3303 
3304         spin_lock(&ctl->tree_lock);
3305         bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3306                                          1, 0);
3307         if (!bitmap_info) {
3308                 info->bitmap = map;
3309                 map = NULL;
3310                 add_new_bitmap(ctl, info, offset);
3311                 bitmap_info = info;
3312                 info = NULL;
3313         }
3314 
3315         bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3316         bytes -= bytes_added;
3317         offset += bytes_added;
3318         spin_unlock(&ctl->tree_lock);
3319 
3320         if (bytes)
3321                 goto again;
3322 
3323         if (info)
3324                 kmem_cache_free(btrfs_free_space_cachep, info);
3325         if (map)
3326                 kfree(map);
3327         return 0;
3328 }
3329 
3330 /*
3331  * Checks to see if the given range is in the free space cache.  This is really
3332  * just used to check the absence of space, so if there is free space in the
3333  * range at all we will return 1.
3334  */
3335 int test_check_exists(struct btrfs_block_group_cache *cache,
3336                       u64 offset, u64 bytes)
3337 {
3338         struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3339         struct btrfs_free_space *info;
3340         int ret = 0;
3341 
3342         spin_lock(&ctl->tree_lock);
3343         info = tree_search_offset(ctl, offset, 0, 0);
3344         if (!info) {
3345                 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3346                                           1, 0);
3347                 if (!info)
3348                         goto out;
3349         }
3350 
3351 have_info:
3352         if (info->bitmap) {
3353                 u64 bit_off, bit_bytes;
3354                 struct rb_node *n;
3355                 struct btrfs_free_space *tmp;
3356 
3357                 bit_off = offset;
3358                 bit_bytes = ctl->unit;
3359                 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes);
3360                 if (!ret) {
3361                         if (bit_off == offset) {
3362                                 ret = 1;
3363                                 goto out;
3364                         } else if (bit_off > offset &&
3365                                    offset + bytes > bit_off) {
3366                                 ret = 1;
3367                                 goto out;
3368                         }
3369                 }
3370 
3371                 n = rb_prev(&info->offset_index);
3372                 while (n) {
3373                         tmp = rb_entry(n, struct btrfs_free_space,
3374                                        offset_index);
3375                         if (tmp->offset + tmp->bytes < offset)
3376                                 break;
3377                         if (offset + bytes < tmp->offset) {
3378                                 n = rb_prev(&info->offset_index);
3379                                 continue;
3380                         }
3381                         info = tmp;
3382                         goto have_info;
3383                 }
3384 
3385                 n = rb_next(&info->offset_index);
3386                 while (n) {
3387                         tmp = rb_entry(n, struct btrfs_free_space,
3388                                        offset_index);
3389                         if (offset + bytes < tmp->offset)
3390                                 break;
3391                         if (tmp->offset + tmp->bytes < offset) {
3392                                 n = rb_next(&info->offset_index);
3393                                 continue;
3394                         }
3395                         info = tmp;
3396                         goto have_info;
3397                 }
3398 
3399                 ret = 0;
3400                 goto out;
3401         }
3402 
3403         if (info->offset == offset) {
3404                 ret = 1;
3405                 goto out;
3406         }
3407 
3408         if (offset > info->offset && offset < info->offset + info->bytes)
3409                 ret = 1;
3410 out:
3411         spin_unlock(&ctl->tree_lock);
3412         return ret;
3413 }
3414 #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3415 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp