18c2ecf20Sopenharmony_ci// SPDX-License-Identifier: GPL-2.0-only 28c2ecf20Sopenharmony_ci/* -*- mode: c; c-basic-offset: 8; -*- 38c2ecf20Sopenharmony_ci * vim: noexpandtab sw=8 ts=8 sts=0: 48c2ecf20Sopenharmony_ci * 58c2ecf20Sopenharmony_ci * reservations.c 68c2ecf20Sopenharmony_ci * 78c2ecf20Sopenharmony_ci * Allocation reservations implementation 88c2ecf20Sopenharmony_ci * 98c2ecf20Sopenharmony_ci * Some code borrowed from fs/ext3/balloc.c and is: 108c2ecf20Sopenharmony_ci * 118c2ecf20Sopenharmony_ci * Copyright (C) 1992, 1993, 1994, 1995 128c2ecf20Sopenharmony_ci * Remy Card (card@masi.ibp.fr) 138c2ecf20Sopenharmony_ci * Laboratoire MASI - Institut Blaise Pascal 148c2ecf20Sopenharmony_ci * Universite Pierre et Marie Curie (Paris VI) 158c2ecf20Sopenharmony_ci * 168c2ecf20Sopenharmony_ci * The rest is copyright (C) 2010 Novell. All rights reserved. 178c2ecf20Sopenharmony_ci */ 188c2ecf20Sopenharmony_ci 198c2ecf20Sopenharmony_ci#include <linux/fs.h> 208c2ecf20Sopenharmony_ci#include <linux/types.h> 218c2ecf20Sopenharmony_ci#include <linux/highmem.h> 228c2ecf20Sopenharmony_ci#include <linux/bitops.h> 238c2ecf20Sopenharmony_ci#include <linux/list.h> 248c2ecf20Sopenharmony_ci 258c2ecf20Sopenharmony_ci#include <cluster/masklog.h> 268c2ecf20Sopenharmony_ci 278c2ecf20Sopenharmony_ci#include "ocfs2.h" 288c2ecf20Sopenharmony_ci#include "ocfs2_trace.h" 298c2ecf20Sopenharmony_ci 308c2ecf20Sopenharmony_ci#ifdef CONFIG_OCFS2_DEBUG_FS 318c2ecf20Sopenharmony_ci#define OCFS2_CHECK_RESERVATIONS 328c2ecf20Sopenharmony_ci#endif 338c2ecf20Sopenharmony_ci 348c2ecf20Sopenharmony_cistatic DEFINE_SPINLOCK(resv_lock); 358c2ecf20Sopenharmony_ci 368c2ecf20Sopenharmony_ciint ocfs2_dir_resv_allowed(struct ocfs2_super *osb) 378c2ecf20Sopenharmony_ci{ 388c2ecf20Sopenharmony_ci return (osb->osb_resv_level && osb->osb_dir_resv_level); 398c2ecf20Sopenharmony_ci} 408c2ecf20Sopenharmony_ci 418c2ecf20Sopenharmony_cistatic unsigned int ocfs2_resv_window_bits(struct ocfs2_reservation_map *resmap, 428c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 438c2ecf20Sopenharmony_ci{ 448c2ecf20Sopenharmony_ci struct ocfs2_super *osb = resmap->m_osb; 458c2ecf20Sopenharmony_ci unsigned int bits; 468c2ecf20Sopenharmony_ci 478c2ecf20Sopenharmony_ci if (!(resv->r_flags & OCFS2_RESV_FLAG_DIR)) { 488c2ecf20Sopenharmony_ci /* 8, 16, 32, 64, 128, 256, 512, 1024 */ 498c2ecf20Sopenharmony_ci bits = 4 << osb->osb_resv_level; 508c2ecf20Sopenharmony_ci } else { 518c2ecf20Sopenharmony_ci bits = 4 << osb->osb_dir_resv_level; 528c2ecf20Sopenharmony_ci } 538c2ecf20Sopenharmony_ci return bits; 548c2ecf20Sopenharmony_ci} 558c2ecf20Sopenharmony_ci 568c2ecf20Sopenharmony_cistatic inline unsigned int ocfs2_resv_end(struct ocfs2_alloc_reservation *resv) 578c2ecf20Sopenharmony_ci{ 588c2ecf20Sopenharmony_ci if (resv->r_len) 598c2ecf20Sopenharmony_ci return resv->r_start + resv->r_len - 1; 608c2ecf20Sopenharmony_ci return resv->r_start; 618c2ecf20Sopenharmony_ci} 628c2ecf20Sopenharmony_ci 638c2ecf20Sopenharmony_cistatic inline int ocfs2_resv_empty(struct ocfs2_alloc_reservation *resv) 648c2ecf20Sopenharmony_ci{ 658c2ecf20Sopenharmony_ci return !!(resv->r_len == 0); 668c2ecf20Sopenharmony_ci} 678c2ecf20Sopenharmony_ci 688c2ecf20Sopenharmony_cistatic inline int ocfs2_resmap_disabled(struct ocfs2_reservation_map *resmap) 698c2ecf20Sopenharmony_ci{ 708c2ecf20Sopenharmony_ci if (resmap->m_osb->osb_resv_level == 0) 718c2ecf20Sopenharmony_ci return 1; 728c2ecf20Sopenharmony_ci return 0; 738c2ecf20Sopenharmony_ci} 748c2ecf20Sopenharmony_ci 758c2ecf20Sopenharmony_cistatic void ocfs2_dump_resv(struct ocfs2_reservation_map *resmap) 768c2ecf20Sopenharmony_ci{ 778c2ecf20Sopenharmony_ci struct ocfs2_super *osb = resmap->m_osb; 788c2ecf20Sopenharmony_ci struct rb_node *node; 798c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv; 808c2ecf20Sopenharmony_ci int i = 0; 818c2ecf20Sopenharmony_ci 828c2ecf20Sopenharmony_ci mlog(ML_NOTICE, "Dumping resmap for device %s. Bitmap length: %u\n", 838c2ecf20Sopenharmony_ci osb->dev_str, resmap->m_bitmap_len); 848c2ecf20Sopenharmony_ci 858c2ecf20Sopenharmony_ci node = rb_first(&resmap->m_reservations); 868c2ecf20Sopenharmony_ci while (node) { 878c2ecf20Sopenharmony_ci resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); 888c2ecf20Sopenharmony_ci 898c2ecf20Sopenharmony_ci mlog(ML_NOTICE, "start: %u\tend: %u\tlen: %u\tlast_start: %u" 908c2ecf20Sopenharmony_ci "\tlast_len: %u\n", resv->r_start, 918c2ecf20Sopenharmony_ci ocfs2_resv_end(resv), resv->r_len, resv->r_last_start, 928c2ecf20Sopenharmony_ci resv->r_last_len); 938c2ecf20Sopenharmony_ci 948c2ecf20Sopenharmony_ci node = rb_next(node); 958c2ecf20Sopenharmony_ci i++; 968c2ecf20Sopenharmony_ci } 978c2ecf20Sopenharmony_ci 988c2ecf20Sopenharmony_ci mlog(ML_NOTICE, "%d reservations found. LRU follows\n", i); 998c2ecf20Sopenharmony_ci 1008c2ecf20Sopenharmony_ci i = 0; 1018c2ecf20Sopenharmony_ci list_for_each_entry(resv, &resmap->m_lru, r_lru) { 1028c2ecf20Sopenharmony_ci mlog(ML_NOTICE, "LRU(%d) start: %u\tend: %u\tlen: %u\t" 1038c2ecf20Sopenharmony_ci "last_start: %u\tlast_len: %u\n", i, resv->r_start, 1048c2ecf20Sopenharmony_ci ocfs2_resv_end(resv), resv->r_len, resv->r_last_start, 1058c2ecf20Sopenharmony_ci resv->r_last_len); 1068c2ecf20Sopenharmony_ci 1078c2ecf20Sopenharmony_ci i++; 1088c2ecf20Sopenharmony_ci } 1098c2ecf20Sopenharmony_ci} 1108c2ecf20Sopenharmony_ci 1118c2ecf20Sopenharmony_ci#ifdef OCFS2_CHECK_RESERVATIONS 1128c2ecf20Sopenharmony_cistatic int ocfs2_validate_resmap_bits(struct ocfs2_reservation_map *resmap, 1138c2ecf20Sopenharmony_ci int i, 1148c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 1158c2ecf20Sopenharmony_ci{ 1168c2ecf20Sopenharmony_ci char *disk_bitmap = resmap->m_disk_bitmap; 1178c2ecf20Sopenharmony_ci unsigned int start = resv->r_start; 1188c2ecf20Sopenharmony_ci unsigned int end = ocfs2_resv_end(resv); 1198c2ecf20Sopenharmony_ci 1208c2ecf20Sopenharmony_ci while (start <= end) { 1218c2ecf20Sopenharmony_ci if (ocfs2_test_bit(start, disk_bitmap)) { 1228c2ecf20Sopenharmony_ci mlog(ML_ERROR, 1238c2ecf20Sopenharmony_ci "reservation %d covers an allocated area " 1248c2ecf20Sopenharmony_ci "starting at bit %u!\n", i, start); 1258c2ecf20Sopenharmony_ci return 1; 1268c2ecf20Sopenharmony_ci } 1278c2ecf20Sopenharmony_ci 1288c2ecf20Sopenharmony_ci start++; 1298c2ecf20Sopenharmony_ci } 1308c2ecf20Sopenharmony_ci return 0; 1318c2ecf20Sopenharmony_ci} 1328c2ecf20Sopenharmony_ci 1338c2ecf20Sopenharmony_cistatic void ocfs2_check_resmap(struct ocfs2_reservation_map *resmap) 1348c2ecf20Sopenharmony_ci{ 1358c2ecf20Sopenharmony_ci unsigned int off = 0; 1368c2ecf20Sopenharmony_ci int i = 0; 1378c2ecf20Sopenharmony_ci struct rb_node *node; 1388c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv; 1398c2ecf20Sopenharmony_ci 1408c2ecf20Sopenharmony_ci node = rb_first(&resmap->m_reservations); 1418c2ecf20Sopenharmony_ci while (node) { 1428c2ecf20Sopenharmony_ci resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); 1438c2ecf20Sopenharmony_ci 1448c2ecf20Sopenharmony_ci if (i > 0 && resv->r_start <= off) { 1458c2ecf20Sopenharmony_ci mlog(ML_ERROR, "reservation %d has bad start off!\n", 1468c2ecf20Sopenharmony_ci i); 1478c2ecf20Sopenharmony_ci goto bad; 1488c2ecf20Sopenharmony_ci } 1498c2ecf20Sopenharmony_ci 1508c2ecf20Sopenharmony_ci if (resv->r_len == 0) { 1518c2ecf20Sopenharmony_ci mlog(ML_ERROR, "reservation %d has no length!\n", 1528c2ecf20Sopenharmony_ci i); 1538c2ecf20Sopenharmony_ci goto bad; 1548c2ecf20Sopenharmony_ci } 1558c2ecf20Sopenharmony_ci 1568c2ecf20Sopenharmony_ci if (resv->r_start > ocfs2_resv_end(resv)) { 1578c2ecf20Sopenharmony_ci mlog(ML_ERROR, "reservation %d has invalid range!\n", 1588c2ecf20Sopenharmony_ci i); 1598c2ecf20Sopenharmony_ci goto bad; 1608c2ecf20Sopenharmony_ci } 1618c2ecf20Sopenharmony_ci 1628c2ecf20Sopenharmony_ci if (ocfs2_resv_end(resv) >= resmap->m_bitmap_len) { 1638c2ecf20Sopenharmony_ci mlog(ML_ERROR, "reservation %d extends past bitmap!\n", 1648c2ecf20Sopenharmony_ci i); 1658c2ecf20Sopenharmony_ci goto bad; 1668c2ecf20Sopenharmony_ci } 1678c2ecf20Sopenharmony_ci 1688c2ecf20Sopenharmony_ci if (ocfs2_validate_resmap_bits(resmap, i, resv)) 1698c2ecf20Sopenharmony_ci goto bad; 1708c2ecf20Sopenharmony_ci 1718c2ecf20Sopenharmony_ci off = ocfs2_resv_end(resv); 1728c2ecf20Sopenharmony_ci node = rb_next(node); 1738c2ecf20Sopenharmony_ci 1748c2ecf20Sopenharmony_ci i++; 1758c2ecf20Sopenharmony_ci } 1768c2ecf20Sopenharmony_ci return; 1778c2ecf20Sopenharmony_ci 1788c2ecf20Sopenharmony_cibad: 1798c2ecf20Sopenharmony_ci ocfs2_dump_resv(resmap); 1808c2ecf20Sopenharmony_ci BUG(); 1818c2ecf20Sopenharmony_ci} 1828c2ecf20Sopenharmony_ci#else 1838c2ecf20Sopenharmony_cistatic inline void ocfs2_check_resmap(struct ocfs2_reservation_map *resmap) 1848c2ecf20Sopenharmony_ci{ 1858c2ecf20Sopenharmony_ci 1868c2ecf20Sopenharmony_ci} 1878c2ecf20Sopenharmony_ci#endif 1888c2ecf20Sopenharmony_ci 1898c2ecf20Sopenharmony_civoid ocfs2_resv_init_once(struct ocfs2_alloc_reservation *resv) 1908c2ecf20Sopenharmony_ci{ 1918c2ecf20Sopenharmony_ci memset(resv, 0, sizeof(*resv)); 1928c2ecf20Sopenharmony_ci INIT_LIST_HEAD(&resv->r_lru); 1938c2ecf20Sopenharmony_ci} 1948c2ecf20Sopenharmony_ci 1958c2ecf20Sopenharmony_civoid ocfs2_resv_set_type(struct ocfs2_alloc_reservation *resv, 1968c2ecf20Sopenharmony_ci unsigned int flags) 1978c2ecf20Sopenharmony_ci{ 1988c2ecf20Sopenharmony_ci BUG_ON(flags & ~OCFS2_RESV_TYPES); 1998c2ecf20Sopenharmony_ci 2008c2ecf20Sopenharmony_ci resv->r_flags |= flags; 2018c2ecf20Sopenharmony_ci} 2028c2ecf20Sopenharmony_ci 2038c2ecf20Sopenharmony_ciint ocfs2_resmap_init(struct ocfs2_super *osb, 2048c2ecf20Sopenharmony_ci struct ocfs2_reservation_map *resmap) 2058c2ecf20Sopenharmony_ci{ 2068c2ecf20Sopenharmony_ci memset(resmap, 0, sizeof(*resmap)); 2078c2ecf20Sopenharmony_ci 2088c2ecf20Sopenharmony_ci resmap->m_osb = osb; 2098c2ecf20Sopenharmony_ci resmap->m_reservations = RB_ROOT; 2108c2ecf20Sopenharmony_ci /* m_bitmap_len is initialized to zero by the above memset. */ 2118c2ecf20Sopenharmony_ci INIT_LIST_HEAD(&resmap->m_lru); 2128c2ecf20Sopenharmony_ci 2138c2ecf20Sopenharmony_ci return 0; 2148c2ecf20Sopenharmony_ci} 2158c2ecf20Sopenharmony_ci 2168c2ecf20Sopenharmony_cistatic void ocfs2_resv_mark_lru(struct ocfs2_reservation_map *resmap, 2178c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 2188c2ecf20Sopenharmony_ci{ 2198c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 2208c2ecf20Sopenharmony_ci 2218c2ecf20Sopenharmony_ci if (!list_empty(&resv->r_lru)) 2228c2ecf20Sopenharmony_ci list_del_init(&resv->r_lru); 2238c2ecf20Sopenharmony_ci 2248c2ecf20Sopenharmony_ci list_add_tail(&resv->r_lru, &resmap->m_lru); 2258c2ecf20Sopenharmony_ci} 2268c2ecf20Sopenharmony_ci 2278c2ecf20Sopenharmony_cistatic void __ocfs2_resv_trunc(struct ocfs2_alloc_reservation *resv) 2288c2ecf20Sopenharmony_ci{ 2298c2ecf20Sopenharmony_ci resv->r_len = 0; 2308c2ecf20Sopenharmony_ci resv->r_start = 0; 2318c2ecf20Sopenharmony_ci} 2328c2ecf20Sopenharmony_ci 2338c2ecf20Sopenharmony_cistatic void ocfs2_resv_remove(struct ocfs2_reservation_map *resmap, 2348c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 2358c2ecf20Sopenharmony_ci{ 2368c2ecf20Sopenharmony_ci if (resv->r_flags & OCFS2_RESV_FLAG_INUSE) { 2378c2ecf20Sopenharmony_ci list_del_init(&resv->r_lru); 2388c2ecf20Sopenharmony_ci rb_erase(&resv->r_node, &resmap->m_reservations); 2398c2ecf20Sopenharmony_ci resv->r_flags &= ~OCFS2_RESV_FLAG_INUSE; 2408c2ecf20Sopenharmony_ci } 2418c2ecf20Sopenharmony_ci} 2428c2ecf20Sopenharmony_ci 2438c2ecf20Sopenharmony_cistatic void __ocfs2_resv_discard(struct ocfs2_reservation_map *resmap, 2448c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 2458c2ecf20Sopenharmony_ci{ 2468c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 2478c2ecf20Sopenharmony_ci 2488c2ecf20Sopenharmony_ci __ocfs2_resv_trunc(resv); 2498c2ecf20Sopenharmony_ci /* 2508c2ecf20Sopenharmony_ci * last_len and last_start no longer make sense if 2518c2ecf20Sopenharmony_ci * we're changing the range of our allocations. 2528c2ecf20Sopenharmony_ci */ 2538c2ecf20Sopenharmony_ci resv->r_last_len = resv->r_last_start = 0; 2548c2ecf20Sopenharmony_ci 2558c2ecf20Sopenharmony_ci ocfs2_resv_remove(resmap, resv); 2568c2ecf20Sopenharmony_ci} 2578c2ecf20Sopenharmony_ci 2588c2ecf20Sopenharmony_ci/* does nothing if 'resv' is null */ 2598c2ecf20Sopenharmony_civoid ocfs2_resv_discard(struct ocfs2_reservation_map *resmap, 2608c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv) 2618c2ecf20Sopenharmony_ci{ 2628c2ecf20Sopenharmony_ci if (resv) { 2638c2ecf20Sopenharmony_ci spin_lock(&resv_lock); 2648c2ecf20Sopenharmony_ci __ocfs2_resv_discard(resmap, resv); 2658c2ecf20Sopenharmony_ci spin_unlock(&resv_lock); 2668c2ecf20Sopenharmony_ci } 2678c2ecf20Sopenharmony_ci} 2688c2ecf20Sopenharmony_ci 2698c2ecf20Sopenharmony_cistatic void ocfs2_resmap_clear_all_resv(struct ocfs2_reservation_map *resmap) 2708c2ecf20Sopenharmony_ci{ 2718c2ecf20Sopenharmony_ci struct rb_node *node; 2728c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv; 2738c2ecf20Sopenharmony_ci 2748c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 2758c2ecf20Sopenharmony_ci 2768c2ecf20Sopenharmony_ci while ((node = rb_last(&resmap->m_reservations)) != NULL) { 2778c2ecf20Sopenharmony_ci resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); 2788c2ecf20Sopenharmony_ci 2798c2ecf20Sopenharmony_ci __ocfs2_resv_discard(resmap, resv); 2808c2ecf20Sopenharmony_ci } 2818c2ecf20Sopenharmony_ci} 2828c2ecf20Sopenharmony_ci 2838c2ecf20Sopenharmony_civoid ocfs2_resmap_restart(struct ocfs2_reservation_map *resmap, 2848c2ecf20Sopenharmony_ci unsigned int clen, char *disk_bitmap) 2858c2ecf20Sopenharmony_ci{ 2868c2ecf20Sopenharmony_ci if (ocfs2_resmap_disabled(resmap)) 2878c2ecf20Sopenharmony_ci return; 2888c2ecf20Sopenharmony_ci 2898c2ecf20Sopenharmony_ci spin_lock(&resv_lock); 2908c2ecf20Sopenharmony_ci 2918c2ecf20Sopenharmony_ci ocfs2_resmap_clear_all_resv(resmap); 2928c2ecf20Sopenharmony_ci resmap->m_bitmap_len = clen; 2938c2ecf20Sopenharmony_ci resmap->m_disk_bitmap = disk_bitmap; 2948c2ecf20Sopenharmony_ci 2958c2ecf20Sopenharmony_ci spin_unlock(&resv_lock); 2968c2ecf20Sopenharmony_ci} 2978c2ecf20Sopenharmony_ci 2988c2ecf20Sopenharmony_civoid ocfs2_resmap_uninit(struct ocfs2_reservation_map *resmap) 2998c2ecf20Sopenharmony_ci{ 3008c2ecf20Sopenharmony_ci /* Does nothing for now. Keep this around for API symmetry */ 3018c2ecf20Sopenharmony_ci} 3028c2ecf20Sopenharmony_ci 3038c2ecf20Sopenharmony_cistatic void ocfs2_resv_insert(struct ocfs2_reservation_map *resmap, 3048c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *new) 3058c2ecf20Sopenharmony_ci{ 3068c2ecf20Sopenharmony_ci struct rb_root *root = &resmap->m_reservations; 3078c2ecf20Sopenharmony_ci struct rb_node *parent = NULL; 3088c2ecf20Sopenharmony_ci struct rb_node **p = &root->rb_node; 3098c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *tmp; 3108c2ecf20Sopenharmony_ci 3118c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 3128c2ecf20Sopenharmony_ci 3138c2ecf20Sopenharmony_ci trace_ocfs2_resv_insert(new->r_start, new->r_len); 3148c2ecf20Sopenharmony_ci 3158c2ecf20Sopenharmony_ci while (*p) { 3168c2ecf20Sopenharmony_ci parent = *p; 3178c2ecf20Sopenharmony_ci 3188c2ecf20Sopenharmony_ci tmp = rb_entry(parent, struct ocfs2_alloc_reservation, r_node); 3198c2ecf20Sopenharmony_ci 3208c2ecf20Sopenharmony_ci if (new->r_start < tmp->r_start) { 3218c2ecf20Sopenharmony_ci p = &(*p)->rb_left; 3228c2ecf20Sopenharmony_ci 3238c2ecf20Sopenharmony_ci /* 3248c2ecf20Sopenharmony_ci * This is a good place to check for 3258c2ecf20Sopenharmony_ci * overlapping reservations. 3268c2ecf20Sopenharmony_ci */ 3278c2ecf20Sopenharmony_ci BUG_ON(ocfs2_resv_end(new) >= tmp->r_start); 3288c2ecf20Sopenharmony_ci } else if (new->r_start > ocfs2_resv_end(tmp)) { 3298c2ecf20Sopenharmony_ci p = &(*p)->rb_right; 3308c2ecf20Sopenharmony_ci } else { 3318c2ecf20Sopenharmony_ci /* This should never happen! */ 3328c2ecf20Sopenharmony_ci mlog(ML_ERROR, "Duplicate reservation window!\n"); 3338c2ecf20Sopenharmony_ci BUG(); 3348c2ecf20Sopenharmony_ci } 3358c2ecf20Sopenharmony_ci } 3368c2ecf20Sopenharmony_ci 3378c2ecf20Sopenharmony_ci rb_link_node(&new->r_node, parent, p); 3388c2ecf20Sopenharmony_ci rb_insert_color(&new->r_node, root); 3398c2ecf20Sopenharmony_ci new->r_flags |= OCFS2_RESV_FLAG_INUSE; 3408c2ecf20Sopenharmony_ci 3418c2ecf20Sopenharmony_ci ocfs2_resv_mark_lru(resmap, new); 3428c2ecf20Sopenharmony_ci 3438c2ecf20Sopenharmony_ci ocfs2_check_resmap(resmap); 3448c2ecf20Sopenharmony_ci} 3458c2ecf20Sopenharmony_ci 3468c2ecf20Sopenharmony_ci/** 3478c2ecf20Sopenharmony_ci * ocfs2_find_resv_lhs() - find the window which contains goal 3488c2ecf20Sopenharmony_ci * @resmap: reservation map to search 3498c2ecf20Sopenharmony_ci * @goal: which bit to search for 3508c2ecf20Sopenharmony_ci * 3518c2ecf20Sopenharmony_ci * If a window containing that goal is not found, we return the window 3528c2ecf20Sopenharmony_ci * which comes before goal. Returns NULL on empty rbtree or no window 3538c2ecf20Sopenharmony_ci * before goal. 3548c2ecf20Sopenharmony_ci */ 3558c2ecf20Sopenharmony_cistatic struct ocfs2_alloc_reservation * 3568c2ecf20Sopenharmony_ciocfs2_find_resv_lhs(struct ocfs2_reservation_map *resmap, unsigned int goal) 3578c2ecf20Sopenharmony_ci{ 3588c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv = NULL; 3598c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *prev_resv = NULL; 3608c2ecf20Sopenharmony_ci struct rb_node *node = resmap->m_reservations.rb_node; 3618c2ecf20Sopenharmony_ci 3628c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 3638c2ecf20Sopenharmony_ci 3648c2ecf20Sopenharmony_ci if (!node) 3658c2ecf20Sopenharmony_ci return NULL; 3668c2ecf20Sopenharmony_ci 3678c2ecf20Sopenharmony_ci node = rb_first(&resmap->m_reservations); 3688c2ecf20Sopenharmony_ci while (node) { 3698c2ecf20Sopenharmony_ci resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); 3708c2ecf20Sopenharmony_ci 3718c2ecf20Sopenharmony_ci if (resv->r_start <= goal && ocfs2_resv_end(resv) >= goal) 3728c2ecf20Sopenharmony_ci break; 3738c2ecf20Sopenharmony_ci 3748c2ecf20Sopenharmony_ci /* Check if we overshot the reservation just before goal? */ 3758c2ecf20Sopenharmony_ci if (resv->r_start > goal) { 3768c2ecf20Sopenharmony_ci resv = prev_resv; 3778c2ecf20Sopenharmony_ci break; 3788c2ecf20Sopenharmony_ci } 3798c2ecf20Sopenharmony_ci 3808c2ecf20Sopenharmony_ci prev_resv = resv; 3818c2ecf20Sopenharmony_ci node = rb_next(node); 3828c2ecf20Sopenharmony_ci } 3838c2ecf20Sopenharmony_ci 3848c2ecf20Sopenharmony_ci return resv; 3858c2ecf20Sopenharmony_ci} 3868c2ecf20Sopenharmony_ci 3878c2ecf20Sopenharmony_ci/* 3888c2ecf20Sopenharmony_ci * We are given a range within the bitmap, which corresponds to a gap 3898c2ecf20Sopenharmony_ci * inside the reservations tree (search_start, search_len). The range 3908c2ecf20Sopenharmony_ci * can be anything from the whole bitmap, to a gap between 3918c2ecf20Sopenharmony_ci * reservations. 3928c2ecf20Sopenharmony_ci * 3938c2ecf20Sopenharmony_ci * The start value of *rstart is insignificant. 3948c2ecf20Sopenharmony_ci * 3958c2ecf20Sopenharmony_ci * This function searches the bitmap range starting at search_start 3968c2ecf20Sopenharmony_ci * with length search_len for a set of contiguous free bits. We try 3978c2ecf20Sopenharmony_ci * to find up to 'wanted' bits, but can sometimes return less. 3988c2ecf20Sopenharmony_ci * 3998c2ecf20Sopenharmony_ci * Returns the length of allocation, 0 if no free bits are found. 4008c2ecf20Sopenharmony_ci * 4018c2ecf20Sopenharmony_ci * *cstart and *clen will also be populated with the result. 4028c2ecf20Sopenharmony_ci */ 4038c2ecf20Sopenharmony_cistatic int ocfs2_resmap_find_free_bits(struct ocfs2_reservation_map *resmap, 4048c2ecf20Sopenharmony_ci unsigned int wanted, 4058c2ecf20Sopenharmony_ci unsigned int search_start, 4068c2ecf20Sopenharmony_ci unsigned int search_len, 4078c2ecf20Sopenharmony_ci unsigned int *rstart, 4088c2ecf20Sopenharmony_ci unsigned int *rlen) 4098c2ecf20Sopenharmony_ci{ 4108c2ecf20Sopenharmony_ci void *bitmap = resmap->m_disk_bitmap; 4118c2ecf20Sopenharmony_ci unsigned int best_start, best_len = 0; 4128c2ecf20Sopenharmony_ci int offset, start, found; 4138c2ecf20Sopenharmony_ci 4148c2ecf20Sopenharmony_ci trace_ocfs2_resmap_find_free_bits_begin(search_start, search_len, 4158c2ecf20Sopenharmony_ci wanted, resmap->m_bitmap_len); 4168c2ecf20Sopenharmony_ci 4178c2ecf20Sopenharmony_ci found = best_start = best_len = 0; 4188c2ecf20Sopenharmony_ci 4198c2ecf20Sopenharmony_ci start = search_start; 4208c2ecf20Sopenharmony_ci while ((offset = ocfs2_find_next_zero_bit(bitmap, resmap->m_bitmap_len, 4218c2ecf20Sopenharmony_ci start)) != -1) { 4228c2ecf20Sopenharmony_ci /* Search reached end of the region */ 4238c2ecf20Sopenharmony_ci if (offset >= (search_start + search_len)) 4248c2ecf20Sopenharmony_ci break; 4258c2ecf20Sopenharmony_ci 4268c2ecf20Sopenharmony_ci if (offset == start) { 4278c2ecf20Sopenharmony_ci /* we found a zero */ 4288c2ecf20Sopenharmony_ci found++; 4298c2ecf20Sopenharmony_ci /* move start to the next bit to test */ 4308c2ecf20Sopenharmony_ci start++; 4318c2ecf20Sopenharmony_ci } else { 4328c2ecf20Sopenharmony_ci /* got a zero after some ones */ 4338c2ecf20Sopenharmony_ci found = 1; 4348c2ecf20Sopenharmony_ci start = offset + 1; 4358c2ecf20Sopenharmony_ci } 4368c2ecf20Sopenharmony_ci if (found > best_len) { 4378c2ecf20Sopenharmony_ci best_len = found; 4388c2ecf20Sopenharmony_ci best_start = start - found; 4398c2ecf20Sopenharmony_ci } 4408c2ecf20Sopenharmony_ci 4418c2ecf20Sopenharmony_ci if (found >= wanted) 4428c2ecf20Sopenharmony_ci break; 4438c2ecf20Sopenharmony_ci } 4448c2ecf20Sopenharmony_ci 4458c2ecf20Sopenharmony_ci if (best_len == 0) 4468c2ecf20Sopenharmony_ci return 0; 4478c2ecf20Sopenharmony_ci 4488c2ecf20Sopenharmony_ci if (best_len >= wanted) 4498c2ecf20Sopenharmony_ci best_len = wanted; 4508c2ecf20Sopenharmony_ci 4518c2ecf20Sopenharmony_ci *rlen = best_len; 4528c2ecf20Sopenharmony_ci *rstart = best_start; 4538c2ecf20Sopenharmony_ci 4548c2ecf20Sopenharmony_ci trace_ocfs2_resmap_find_free_bits_end(best_start, best_len); 4558c2ecf20Sopenharmony_ci 4568c2ecf20Sopenharmony_ci return *rlen; 4578c2ecf20Sopenharmony_ci} 4588c2ecf20Sopenharmony_ci 4598c2ecf20Sopenharmony_cistatic void __ocfs2_resv_find_window(struct ocfs2_reservation_map *resmap, 4608c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 4618c2ecf20Sopenharmony_ci unsigned int goal, unsigned int wanted) 4628c2ecf20Sopenharmony_ci{ 4638c2ecf20Sopenharmony_ci struct rb_root *root = &resmap->m_reservations; 4648c2ecf20Sopenharmony_ci unsigned int gap_start, gap_end, gap_len; 4658c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *prev_resv, *next_resv; 4668c2ecf20Sopenharmony_ci struct rb_node *prev, *next; 4678c2ecf20Sopenharmony_ci unsigned int cstart, clen; 4688c2ecf20Sopenharmony_ci unsigned int best_start = 0, best_len = 0; 4698c2ecf20Sopenharmony_ci 4708c2ecf20Sopenharmony_ci /* 4718c2ecf20Sopenharmony_ci * Nasty cases to consider: 4728c2ecf20Sopenharmony_ci * 4738c2ecf20Sopenharmony_ci * - rbtree is empty 4748c2ecf20Sopenharmony_ci * - our window should be first in all reservations 4758c2ecf20Sopenharmony_ci * - our window should be last in all reservations 4768c2ecf20Sopenharmony_ci * - need to make sure we don't go past end of bitmap 4778c2ecf20Sopenharmony_ci */ 4788c2ecf20Sopenharmony_ci trace_ocfs2_resv_find_window_begin(resv->r_start, ocfs2_resv_end(resv), 4798c2ecf20Sopenharmony_ci goal, wanted, RB_EMPTY_ROOT(root)); 4808c2ecf20Sopenharmony_ci 4818c2ecf20Sopenharmony_ci assert_spin_locked(&resv_lock); 4828c2ecf20Sopenharmony_ci 4838c2ecf20Sopenharmony_ci if (RB_EMPTY_ROOT(root)) { 4848c2ecf20Sopenharmony_ci /* 4858c2ecf20Sopenharmony_ci * Easiest case - empty tree. We can just take 4868c2ecf20Sopenharmony_ci * whatever window of free bits we want. 4878c2ecf20Sopenharmony_ci */ 4888c2ecf20Sopenharmony_ci clen = ocfs2_resmap_find_free_bits(resmap, wanted, goal, 4898c2ecf20Sopenharmony_ci resmap->m_bitmap_len - goal, 4908c2ecf20Sopenharmony_ci &cstart, &clen); 4918c2ecf20Sopenharmony_ci 4928c2ecf20Sopenharmony_ci /* 4938c2ecf20Sopenharmony_ci * This should never happen - the local alloc window 4948c2ecf20Sopenharmony_ci * will always have free bits when we're called. 4958c2ecf20Sopenharmony_ci */ 4968c2ecf20Sopenharmony_ci BUG_ON(goal == 0 && clen == 0); 4978c2ecf20Sopenharmony_ci 4988c2ecf20Sopenharmony_ci if (clen == 0) 4998c2ecf20Sopenharmony_ci return; 5008c2ecf20Sopenharmony_ci 5018c2ecf20Sopenharmony_ci resv->r_start = cstart; 5028c2ecf20Sopenharmony_ci resv->r_len = clen; 5038c2ecf20Sopenharmony_ci 5048c2ecf20Sopenharmony_ci ocfs2_resv_insert(resmap, resv); 5058c2ecf20Sopenharmony_ci return; 5068c2ecf20Sopenharmony_ci } 5078c2ecf20Sopenharmony_ci 5088c2ecf20Sopenharmony_ci prev_resv = ocfs2_find_resv_lhs(resmap, goal); 5098c2ecf20Sopenharmony_ci 5108c2ecf20Sopenharmony_ci if (prev_resv == NULL) { 5118c2ecf20Sopenharmony_ci /* 5128c2ecf20Sopenharmony_ci * A NULL here means that the search code couldn't 5138c2ecf20Sopenharmony_ci * find a window that starts before goal. 5148c2ecf20Sopenharmony_ci * 5158c2ecf20Sopenharmony_ci * However, we can take the first window after goal, 5168c2ecf20Sopenharmony_ci * which is also by definition, the leftmost window in 5178c2ecf20Sopenharmony_ci * the entire tree. If we can find free bits in the 5188c2ecf20Sopenharmony_ci * gap between goal and the LHS window, then the 5198c2ecf20Sopenharmony_ci * reservation can safely be placed there. 5208c2ecf20Sopenharmony_ci * 5218c2ecf20Sopenharmony_ci * Otherwise we fall back to a linear search, checking 5228c2ecf20Sopenharmony_ci * the gaps in between windows for a place to 5238c2ecf20Sopenharmony_ci * allocate. 5248c2ecf20Sopenharmony_ci */ 5258c2ecf20Sopenharmony_ci 5268c2ecf20Sopenharmony_ci next = rb_first(root); 5278c2ecf20Sopenharmony_ci next_resv = rb_entry(next, struct ocfs2_alloc_reservation, 5288c2ecf20Sopenharmony_ci r_node); 5298c2ecf20Sopenharmony_ci 5308c2ecf20Sopenharmony_ci /* 5318c2ecf20Sopenharmony_ci * The search should never return such a window. (see 5328c2ecf20Sopenharmony_ci * comment above 5338c2ecf20Sopenharmony_ci */ 5348c2ecf20Sopenharmony_ci if (next_resv->r_start <= goal) { 5358c2ecf20Sopenharmony_ci mlog(ML_ERROR, "goal: %u next_resv: start %u len %u\n", 5368c2ecf20Sopenharmony_ci goal, next_resv->r_start, next_resv->r_len); 5378c2ecf20Sopenharmony_ci ocfs2_dump_resv(resmap); 5388c2ecf20Sopenharmony_ci BUG(); 5398c2ecf20Sopenharmony_ci } 5408c2ecf20Sopenharmony_ci 5418c2ecf20Sopenharmony_ci clen = ocfs2_resmap_find_free_bits(resmap, wanted, goal, 5428c2ecf20Sopenharmony_ci next_resv->r_start - goal, 5438c2ecf20Sopenharmony_ci &cstart, &clen); 5448c2ecf20Sopenharmony_ci if (clen) { 5458c2ecf20Sopenharmony_ci best_len = clen; 5468c2ecf20Sopenharmony_ci best_start = cstart; 5478c2ecf20Sopenharmony_ci if (best_len == wanted) 5488c2ecf20Sopenharmony_ci goto out_insert; 5498c2ecf20Sopenharmony_ci } 5508c2ecf20Sopenharmony_ci 5518c2ecf20Sopenharmony_ci prev_resv = next_resv; 5528c2ecf20Sopenharmony_ci next_resv = NULL; 5538c2ecf20Sopenharmony_ci } 5548c2ecf20Sopenharmony_ci 5558c2ecf20Sopenharmony_ci trace_ocfs2_resv_find_window_prev(prev_resv->r_start, 5568c2ecf20Sopenharmony_ci ocfs2_resv_end(prev_resv)); 5578c2ecf20Sopenharmony_ci 5588c2ecf20Sopenharmony_ci prev = &prev_resv->r_node; 5598c2ecf20Sopenharmony_ci 5608c2ecf20Sopenharmony_ci /* Now we do a linear search for a window, starting at 'prev_rsv' */ 5618c2ecf20Sopenharmony_ci while (1) { 5628c2ecf20Sopenharmony_ci next = rb_next(prev); 5638c2ecf20Sopenharmony_ci if (next) { 5648c2ecf20Sopenharmony_ci next_resv = rb_entry(next, 5658c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation, 5668c2ecf20Sopenharmony_ci r_node); 5678c2ecf20Sopenharmony_ci 5688c2ecf20Sopenharmony_ci gap_start = ocfs2_resv_end(prev_resv) + 1; 5698c2ecf20Sopenharmony_ci gap_end = next_resv->r_start - 1; 5708c2ecf20Sopenharmony_ci gap_len = gap_end - gap_start + 1; 5718c2ecf20Sopenharmony_ci } else { 5728c2ecf20Sopenharmony_ci /* 5738c2ecf20Sopenharmony_ci * We're at the rightmost edge of the 5748c2ecf20Sopenharmony_ci * tree. See if a reservation between this 5758c2ecf20Sopenharmony_ci * window and the end of the bitmap will work. 5768c2ecf20Sopenharmony_ci */ 5778c2ecf20Sopenharmony_ci gap_start = ocfs2_resv_end(prev_resv) + 1; 5788c2ecf20Sopenharmony_ci gap_len = resmap->m_bitmap_len - gap_start; 5798c2ecf20Sopenharmony_ci gap_end = resmap->m_bitmap_len - 1; 5808c2ecf20Sopenharmony_ci } 5818c2ecf20Sopenharmony_ci 5828c2ecf20Sopenharmony_ci trace_ocfs2_resv_find_window_next(next ? next_resv->r_start: -1, 5838c2ecf20Sopenharmony_ci next ? ocfs2_resv_end(next_resv) : -1); 5848c2ecf20Sopenharmony_ci /* 5858c2ecf20Sopenharmony_ci * No need to check this gap if we have already found 5868c2ecf20Sopenharmony_ci * a larger region of free bits. 5878c2ecf20Sopenharmony_ci */ 5888c2ecf20Sopenharmony_ci if (gap_len <= best_len) 5898c2ecf20Sopenharmony_ci goto next_resv; 5908c2ecf20Sopenharmony_ci 5918c2ecf20Sopenharmony_ci clen = ocfs2_resmap_find_free_bits(resmap, wanted, gap_start, 5928c2ecf20Sopenharmony_ci gap_len, &cstart, &clen); 5938c2ecf20Sopenharmony_ci if (clen == wanted) { 5948c2ecf20Sopenharmony_ci best_len = clen; 5958c2ecf20Sopenharmony_ci best_start = cstart; 5968c2ecf20Sopenharmony_ci goto out_insert; 5978c2ecf20Sopenharmony_ci } else if (clen > best_len) { 5988c2ecf20Sopenharmony_ci best_len = clen; 5998c2ecf20Sopenharmony_ci best_start = cstart; 6008c2ecf20Sopenharmony_ci } 6018c2ecf20Sopenharmony_ci 6028c2ecf20Sopenharmony_cinext_resv: 6038c2ecf20Sopenharmony_ci if (!next) 6048c2ecf20Sopenharmony_ci break; 6058c2ecf20Sopenharmony_ci 6068c2ecf20Sopenharmony_ci prev = next; 6078c2ecf20Sopenharmony_ci prev_resv = rb_entry(prev, struct ocfs2_alloc_reservation, 6088c2ecf20Sopenharmony_ci r_node); 6098c2ecf20Sopenharmony_ci } 6108c2ecf20Sopenharmony_ci 6118c2ecf20Sopenharmony_ciout_insert: 6128c2ecf20Sopenharmony_ci if (best_len) { 6138c2ecf20Sopenharmony_ci resv->r_start = best_start; 6148c2ecf20Sopenharmony_ci resv->r_len = best_len; 6158c2ecf20Sopenharmony_ci ocfs2_resv_insert(resmap, resv); 6168c2ecf20Sopenharmony_ci } 6178c2ecf20Sopenharmony_ci} 6188c2ecf20Sopenharmony_ci 6198c2ecf20Sopenharmony_cistatic void ocfs2_cannibalize_resv(struct ocfs2_reservation_map *resmap, 6208c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 6218c2ecf20Sopenharmony_ci unsigned int wanted) 6228c2ecf20Sopenharmony_ci{ 6238c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *lru_resv; 6248c2ecf20Sopenharmony_ci int tmpwindow = !!(resv->r_flags & OCFS2_RESV_FLAG_TMP); 6258c2ecf20Sopenharmony_ci unsigned int min_bits; 6268c2ecf20Sopenharmony_ci 6278c2ecf20Sopenharmony_ci if (!tmpwindow) 6288c2ecf20Sopenharmony_ci min_bits = ocfs2_resv_window_bits(resmap, resv) >> 1; 6298c2ecf20Sopenharmony_ci else 6308c2ecf20Sopenharmony_ci min_bits = wanted; /* We at know the temp window will use all 6318c2ecf20Sopenharmony_ci * of these bits */ 6328c2ecf20Sopenharmony_ci 6338c2ecf20Sopenharmony_ci /* 6348c2ecf20Sopenharmony_ci * Take the first reservation off the LRU as our 'target'. We 6358c2ecf20Sopenharmony_ci * don't try to be smart about it. There might be a case for 6368c2ecf20Sopenharmony_ci * searching based on size but I don't have enough data to be 6378c2ecf20Sopenharmony_ci * sure. --Mark (3/16/2010) 6388c2ecf20Sopenharmony_ci */ 6398c2ecf20Sopenharmony_ci lru_resv = list_first_entry(&resmap->m_lru, 6408c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation, r_lru); 6418c2ecf20Sopenharmony_ci 6428c2ecf20Sopenharmony_ci trace_ocfs2_cannibalize_resv_begin(lru_resv->r_start, 6438c2ecf20Sopenharmony_ci lru_resv->r_len, 6448c2ecf20Sopenharmony_ci ocfs2_resv_end(lru_resv)); 6458c2ecf20Sopenharmony_ci 6468c2ecf20Sopenharmony_ci /* 6478c2ecf20Sopenharmony_ci * Cannibalize (some or all) of the target reservation and 6488c2ecf20Sopenharmony_ci * feed it to the current window. 6498c2ecf20Sopenharmony_ci */ 6508c2ecf20Sopenharmony_ci if (lru_resv->r_len <= min_bits) { 6518c2ecf20Sopenharmony_ci /* 6528c2ecf20Sopenharmony_ci * Discard completely if size is less than or equal to a 6538c2ecf20Sopenharmony_ci * reasonable threshold - 50% of window bits for non temporary 6548c2ecf20Sopenharmony_ci * windows. 6558c2ecf20Sopenharmony_ci */ 6568c2ecf20Sopenharmony_ci resv->r_start = lru_resv->r_start; 6578c2ecf20Sopenharmony_ci resv->r_len = lru_resv->r_len; 6588c2ecf20Sopenharmony_ci 6598c2ecf20Sopenharmony_ci __ocfs2_resv_discard(resmap, lru_resv); 6608c2ecf20Sopenharmony_ci } else { 6618c2ecf20Sopenharmony_ci unsigned int shrink; 6628c2ecf20Sopenharmony_ci if (tmpwindow) 6638c2ecf20Sopenharmony_ci shrink = min_bits; 6648c2ecf20Sopenharmony_ci else 6658c2ecf20Sopenharmony_ci shrink = lru_resv->r_len / 2; 6668c2ecf20Sopenharmony_ci 6678c2ecf20Sopenharmony_ci lru_resv->r_len -= shrink; 6688c2ecf20Sopenharmony_ci 6698c2ecf20Sopenharmony_ci resv->r_start = ocfs2_resv_end(lru_resv) + 1; 6708c2ecf20Sopenharmony_ci resv->r_len = shrink; 6718c2ecf20Sopenharmony_ci } 6728c2ecf20Sopenharmony_ci 6738c2ecf20Sopenharmony_ci trace_ocfs2_cannibalize_resv_end(resv->r_start, ocfs2_resv_end(resv), 6748c2ecf20Sopenharmony_ci resv->r_len, resv->r_last_start, 6758c2ecf20Sopenharmony_ci resv->r_last_len); 6768c2ecf20Sopenharmony_ci 6778c2ecf20Sopenharmony_ci ocfs2_resv_insert(resmap, resv); 6788c2ecf20Sopenharmony_ci} 6798c2ecf20Sopenharmony_ci 6808c2ecf20Sopenharmony_cistatic void ocfs2_resv_find_window(struct ocfs2_reservation_map *resmap, 6818c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 6828c2ecf20Sopenharmony_ci unsigned int wanted) 6838c2ecf20Sopenharmony_ci{ 6848c2ecf20Sopenharmony_ci unsigned int goal = 0; 6858c2ecf20Sopenharmony_ci 6868c2ecf20Sopenharmony_ci BUG_ON(!ocfs2_resv_empty(resv)); 6878c2ecf20Sopenharmony_ci 6888c2ecf20Sopenharmony_ci /* 6898c2ecf20Sopenharmony_ci * Begin by trying to get a window as close to the previous 6908c2ecf20Sopenharmony_ci * one as possible. Using the most recent allocation as a 6918c2ecf20Sopenharmony_ci * start goal makes sense. 6928c2ecf20Sopenharmony_ci */ 6938c2ecf20Sopenharmony_ci if (resv->r_last_len) { 6948c2ecf20Sopenharmony_ci goal = resv->r_last_start + resv->r_last_len; 6958c2ecf20Sopenharmony_ci if (goal >= resmap->m_bitmap_len) 6968c2ecf20Sopenharmony_ci goal = 0; 6978c2ecf20Sopenharmony_ci } 6988c2ecf20Sopenharmony_ci 6998c2ecf20Sopenharmony_ci __ocfs2_resv_find_window(resmap, resv, goal, wanted); 7008c2ecf20Sopenharmony_ci 7018c2ecf20Sopenharmony_ci /* Search from last alloc didn't work, try once more from beginning. */ 7028c2ecf20Sopenharmony_ci if (ocfs2_resv_empty(resv) && goal != 0) 7038c2ecf20Sopenharmony_ci __ocfs2_resv_find_window(resmap, resv, 0, wanted); 7048c2ecf20Sopenharmony_ci 7058c2ecf20Sopenharmony_ci if (ocfs2_resv_empty(resv)) { 7068c2ecf20Sopenharmony_ci /* 7078c2ecf20Sopenharmony_ci * Still empty? Pull oldest one off the LRU, remove it from 7088c2ecf20Sopenharmony_ci * tree, put this one in it's place. 7098c2ecf20Sopenharmony_ci */ 7108c2ecf20Sopenharmony_ci ocfs2_cannibalize_resv(resmap, resv, wanted); 7118c2ecf20Sopenharmony_ci } 7128c2ecf20Sopenharmony_ci 7138c2ecf20Sopenharmony_ci BUG_ON(ocfs2_resv_empty(resv)); 7148c2ecf20Sopenharmony_ci} 7158c2ecf20Sopenharmony_ci 7168c2ecf20Sopenharmony_ciint ocfs2_resmap_resv_bits(struct ocfs2_reservation_map *resmap, 7178c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 7188c2ecf20Sopenharmony_ci int *cstart, int *clen) 7198c2ecf20Sopenharmony_ci{ 7208c2ecf20Sopenharmony_ci if (resv == NULL || ocfs2_resmap_disabled(resmap)) 7218c2ecf20Sopenharmony_ci return -ENOSPC; 7228c2ecf20Sopenharmony_ci 7238c2ecf20Sopenharmony_ci spin_lock(&resv_lock); 7248c2ecf20Sopenharmony_ci 7258c2ecf20Sopenharmony_ci if (ocfs2_resv_empty(resv)) { 7268c2ecf20Sopenharmony_ci /* 7278c2ecf20Sopenharmony_ci * We don't want to over-allocate for temporary 7288c2ecf20Sopenharmony_ci * windows. Otherwise, we run the risk of fragmenting the 7298c2ecf20Sopenharmony_ci * allocation space. 7308c2ecf20Sopenharmony_ci */ 7318c2ecf20Sopenharmony_ci unsigned int wanted = ocfs2_resv_window_bits(resmap, resv); 7328c2ecf20Sopenharmony_ci 7338c2ecf20Sopenharmony_ci if ((resv->r_flags & OCFS2_RESV_FLAG_TMP) || wanted < *clen) 7348c2ecf20Sopenharmony_ci wanted = *clen; 7358c2ecf20Sopenharmony_ci 7368c2ecf20Sopenharmony_ci /* 7378c2ecf20Sopenharmony_ci * Try to get a window here. If it works, we must fall 7388c2ecf20Sopenharmony_ci * through and test the bitmap . This avoids some 7398c2ecf20Sopenharmony_ci * ping-ponging of windows due to non-reserved space 7408c2ecf20Sopenharmony_ci * being allocation before we initialize a window for 7418c2ecf20Sopenharmony_ci * that inode. 7428c2ecf20Sopenharmony_ci */ 7438c2ecf20Sopenharmony_ci ocfs2_resv_find_window(resmap, resv, wanted); 7448c2ecf20Sopenharmony_ci trace_ocfs2_resmap_resv_bits(resv->r_start, resv->r_len); 7458c2ecf20Sopenharmony_ci } 7468c2ecf20Sopenharmony_ci 7478c2ecf20Sopenharmony_ci BUG_ON(ocfs2_resv_empty(resv)); 7488c2ecf20Sopenharmony_ci 7498c2ecf20Sopenharmony_ci *cstart = resv->r_start; 7508c2ecf20Sopenharmony_ci *clen = resv->r_len; 7518c2ecf20Sopenharmony_ci 7528c2ecf20Sopenharmony_ci spin_unlock(&resv_lock); 7538c2ecf20Sopenharmony_ci return 0; 7548c2ecf20Sopenharmony_ci} 7558c2ecf20Sopenharmony_ci 7568c2ecf20Sopenharmony_cistatic void 7578c2ecf20Sopenharmony_ci ocfs2_adjust_resv_from_alloc(struct ocfs2_reservation_map *resmap, 7588c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 7598c2ecf20Sopenharmony_ci unsigned int start, unsigned int end) 7608c2ecf20Sopenharmony_ci{ 7618c2ecf20Sopenharmony_ci unsigned int rhs = 0; 7628c2ecf20Sopenharmony_ci unsigned int old_end = ocfs2_resv_end(resv); 7638c2ecf20Sopenharmony_ci 7648c2ecf20Sopenharmony_ci BUG_ON(start != resv->r_start || old_end < end); 7658c2ecf20Sopenharmony_ci 7668c2ecf20Sopenharmony_ci /* 7678c2ecf20Sopenharmony_ci * Completely used? We can remove it then. 7688c2ecf20Sopenharmony_ci */ 7698c2ecf20Sopenharmony_ci if (old_end == end) { 7708c2ecf20Sopenharmony_ci __ocfs2_resv_discard(resmap, resv); 7718c2ecf20Sopenharmony_ci return; 7728c2ecf20Sopenharmony_ci } 7738c2ecf20Sopenharmony_ci 7748c2ecf20Sopenharmony_ci rhs = old_end - end; 7758c2ecf20Sopenharmony_ci 7768c2ecf20Sopenharmony_ci /* 7778c2ecf20Sopenharmony_ci * This should have been trapped above. 7788c2ecf20Sopenharmony_ci */ 7798c2ecf20Sopenharmony_ci BUG_ON(rhs == 0); 7808c2ecf20Sopenharmony_ci 7818c2ecf20Sopenharmony_ci resv->r_start = end + 1; 7828c2ecf20Sopenharmony_ci resv->r_len = old_end - resv->r_start + 1; 7838c2ecf20Sopenharmony_ci} 7848c2ecf20Sopenharmony_ci 7858c2ecf20Sopenharmony_civoid ocfs2_resmap_claimed_bits(struct ocfs2_reservation_map *resmap, 7868c2ecf20Sopenharmony_ci struct ocfs2_alloc_reservation *resv, 7878c2ecf20Sopenharmony_ci u32 cstart, u32 clen) 7888c2ecf20Sopenharmony_ci{ 7898c2ecf20Sopenharmony_ci unsigned int cend = cstart + clen - 1; 7908c2ecf20Sopenharmony_ci 7918c2ecf20Sopenharmony_ci if (resmap == NULL || ocfs2_resmap_disabled(resmap)) 7928c2ecf20Sopenharmony_ci return; 7938c2ecf20Sopenharmony_ci 7948c2ecf20Sopenharmony_ci if (resv == NULL) 7958c2ecf20Sopenharmony_ci return; 7968c2ecf20Sopenharmony_ci 7978c2ecf20Sopenharmony_ci BUG_ON(cstart != resv->r_start); 7988c2ecf20Sopenharmony_ci 7998c2ecf20Sopenharmony_ci spin_lock(&resv_lock); 8008c2ecf20Sopenharmony_ci 8018c2ecf20Sopenharmony_ci trace_ocfs2_resmap_claimed_bits_begin(cstart, cend, clen, resv->r_start, 8028c2ecf20Sopenharmony_ci ocfs2_resv_end(resv), resv->r_len, 8038c2ecf20Sopenharmony_ci resv->r_last_start, 8048c2ecf20Sopenharmony_ci resv->r_last_len); 8058c2ecf20Sopenharmony_ci 8068c2ecf20Sopenharmony_ci BUG_ON(cstart < resv->r_start); 8078c2ecf20Sopenharmony_ci BUG_ON(cstart > ocfs2_resv_end(resv)); 8088c2ecf20Sopenharmony_ci BUG_ON(cend > ocfs2_resv_end(resv)); 8098c2ecf20Sopenharmony_ci 8108c2ecf20Sopenharmony_ci ocfs2_adjust_resv_from_alloc(resmap, resv, cstart, cend); 8118c2ecf20Sopenharmony_ci resv->r_last_start = cstart; 8128c2ecf20Sopenharmony_ci resv->r_last_len = clen; 8138c2ecf20Sopenharmony_ci 8148c2ecf20Sopenharmony_ci /* 8158c2ecf20Sopenharmony_ci * May have been discarded above from 8168c2ecf20Sopenharmony_ci * ocfs2_adjust_resv_from_alloc(). 8178c2ecf20Sopenharmony_ci */ 8188c2ecf20Sopenharmony_ci if (!ocfs2_resv_empty(resv)) 8198c2ecf20Sopenharmony_ci ocfs2_resv_mark_lru(resmap, resv); 8208c2ecf20Sopenharmony_ci 8218c2ecf20Sopenharmony_ci trace_ocfs2_resmap_claimed_bits_end(resv->r_start, ocfs2_resv_end(resv), 8228c2ecf20Sopenharmony_ci resv->r_len, resv->r_last_start, 8238c2ecf20Sopenharmony_ci resv->r_last_len); 8248c2ecf20Sopenharmony_ci 8258c2ecf20Sopenharmony_ci ocfs2_check_resmap(resmap); 8268c2ecf20Sopenharmony_ci 8278c2ecf20Sopenharmony_ci spin_unlock(&resv_lock); 8288c2ecf20Sopenharmony_ci} 829