path: root/fs/ntfs3/bitmap.c

// SPDX-License-Identifier: GPL-2.0
/*
 *
 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
 *
 * This code builds two trees of free clusters extents.
 * Trees are sorted by start of extent and by length of extent.
 * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees.
 * In extreme case code reads on-disk bitmap to find free clusters.
 *
 */

#include <linux/buffer_head.h>
#include <linux/fs.h>
#include <linux/kernel.h>

#include "ntfs.h"
#include "ntfs_fs.h"

/*
 * Maximum number of extents in tree.
 */
#define NTFS_MAX_WND_EXTENTS (32u * 1024u)

struct rb_node_key {
	struct rb_node node;
	size_t key;
};

struct e_node {
	struct rb_node_key start; /* Tree sorted by start. */
	struct rb_node_key count; /* Tree sorted by len. */
};

static int wnd_rescan(struct wnd_bitmap *wnd);
static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw);
static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits);

static struct kmem_cache *ntfs_enode_cachep;

int __init ntfs3_init_bitmap(void)
{
	ntfs_enode_cachep = kmem_cache_create("ntfs3_enode_cache",
					      sizeof(struct e_node), 0,
					      SLAB_RECLAIM_ACCOUNT, NULL);
	return ntfs_enode_cachep ? 0 : -ENOMEM;
}

void ntfs3_exit_bitmap(void)
{
	kmem_cache_destroy(ntfs_enode_cachep);
}

/*
 * wnd_scan
 *
 * b_pos + b_len - biggest fragment.
 * Scan range [wpos wbits) window @buf.
 *
 * Return: -1 if not found.
 */
static size_t wnd_scan(const void *buf, size_t wbit, u32 wpos, u32 wend,
		       size_t to_alloc, size_t *prev_tail, size_t *b_pos,
		       size_t *b_len)
{
	while (wpos < wend) {
		size_t free_len;
		u32 free_bits, end;
		u32 used = find_next_zero_bit_le(buf, wend, wpos);

		if (used >= wend) {
			if (*b_len < *prev_tail) {
				*b_pos = wbit - *prev_tail;
				*b_len = *prev_tail;
			}

			*prev_tail = 0;
			return -1;
		}

		if (used > wpos) {
			wpos = used;
			if (*b_len < *prev_tail) {
				*b_pos = wbit - *prev_tail;
				*b_len = *prev_tail;
			}

			*prev_tail = 0;
		}

		/*
		 * Now we have a fragment [wpos, wend) staring with 0.
		 */
		end = wpos + to_alloc - *prev_tail;
		free_bits = find_next_bit_le(buf, min(end, wend), wpos);

		free_len = *prev_tail + free_bits - wpos;

		if (*b_len < free_len) {
			*b_pos = wbit + wpos - *prev_tail;
			*b_len = free_len;
		}

		if (free_len >= to_alloc)
			return wbit + wpos - *prev_tail;

		if (free_bits >= wend) {
			*prev_tail += free_bits - wpos;
			return -1;
		}

		wpos = free_bits + 1;

		*prev_tail = 0;
	}

	return -1;
}

/*
 * wnd_close - Frees all resources.
 */
void wnd_close(struct wnd_bitmap *wnd)
{
	struct rb_node *node, *next;

	kvfree(wnd->free_bits);
	wnd->free_bits = NULL;
	run_close(&wnd->run);

	node = rb_first(&wnd->start_tree);

	while (node) {
		next = rb_next(node);
		rb_erase(node, &wnd->start_tree);
		kmem_cache_free(ntfs_enode_cachep,
				rb_entry(node, struct e_node, start.node));
		node = next;
	}
}

static struct rb_node *rb_lookup(struct rb_root *root, size_t v)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *r = NULL;

	while (*p) {
		struct rb_node_key *k;

		k = rb_entry(*p, struct rb_node_key, node);
		if (v < k->key) {
			p = &(*p)->rb_left;
		} else if (v > k->key) {
			r = &k->node;
			p = &(*p)->rb_right;
		} else {
			return &k->node;
		}
	}

	return r;
}

/*
 * rb_insert_count - Helper function to insert special kind of 'count' tree.
 */
static inline bool rb_insert_count(struct rb_root *root, struct e_node *e)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	size_t e_ckey = e->count.key;
	size_t e_skey = e->start.key;

	while (*p) {
		struct e_node *k =
			rb_entry(parent = *p, struct e_node, count.node);

		if (e_ckey > k->count.key) {
			p = &(*p)->rb_left;
		} else if (e_ckey < k->count.key) {
			p = &(*p)->rb_right;
		} else if (e_skey < k->start.key) {
			p = &(*p)->rb_left;
		} else if (e_skey > k->start.key) {
			p = &(*p)->rb_right;
		} else {
			WARN_ON(1);
			return false;
		}
	}

	rb_link_node(&e->count.node, parent, p);
	rb_insert_color(&e->count.node, root);
	return true;
}

/*
 * rb_insert_start - Helper function to insert special kind of 'count' tree.
 */
static inline bool rb_insert_start(struct rb_root *root, struct e_node *e)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	size_t e_skey = e->start.key;

	while (*p) {
		struct e_node *k;

		parent = *p;

		k = rb_entry(parent, struct e_node, start.node);
		if (e_skey < k->start.key) {
			p = &(*p)->rb_left;
		} else if (e_skey > k->start.key) {
			p = &(*p)->rb_right;
		} else {
			WARN_ON(1);
			return false;
		}
	}

	rb_link_node(&e->start.node, parent, p);
	rb_insert_color(&e->start.node, root);
	return true;
}

/*
 * wnd_add_free_ext - Adds a new extent of free space.
 * @build:	1 when building tree.
 */
static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len,
			     bool build)
{
	struct e_node *e, *e0 = NULL;
	size_t ib, end_in = bit + len;
	struct rb_node *n;

	if (build) {
		/* Use extent_min to filter too short extents. */
		if (wnd->count >= NTFS_MAX_WND_EXTENTS &&
		    len <= wnd->extent_min) {
			wnd->uptodated = -1;
			return;
		}
	} else {
		/* Try to find extent before 'bit'. */
		n = rb_lookup(&wnd->start_tree, bit);

		if (!n) {
			n = rb_first(&wnd->start_tree);
		} else {
			e = rb_entry(n, struct e_node, start.node);
			n = rb_next(n);
			if (e->start.key + e->count.key == bit) {
				/* Remove left. */
				bit = e->start.key;
				len += e->count.key;
				rb_erase(&e->start.node, &wnd->start_tree);
				rb_erase(&e->count.node, &wnd->count_tree);
				wnd->count -= 1;
				e0 = e;
			}
		}

		while (n) {
			size_t next_end;

			e = rb_entry(n, struct e_node, start.node);
			next_end = e->start.key + e->count.key;
			if (e->start.key > end_in)
				break;

			/* Remove right. */
			n = rb_next(n);
			len += next_end - end_in;
			end_in = next_end;
			rb_erase(&e->start.node, &wnd->start_tree);
			rb_erase(&e->count.node, &wnd->count_tree);
			wnd->count -= 1;

			if (!e0)
				e0 = e;
			else
				kmem_cache_free(ntfs_enode_cachep, e);
		}

		if (wnd->uptodated !