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