linux/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 …

struct rb_node_key { … };

struct e_node { … };

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)
{ … }

void ntfs3_exit_bitmap(void)
{ … }

/*
 * 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)
{ … }

/*
 * wnd_close - Frees all resources.
 */
void wnd_close(struct wnd_bitmap *wnd)
{ … }

static struct rb_node *rb_lookup(struct rb_root *root, size_t v)
{ … }

/*
 * 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)
{ … }

/*
 * 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)
{ … }

/*
 * 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)
{ … }

/*
 * wnd_remove_free_ext - Remove a run from the cached free space.
 */
static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len)
{ … }

/*
 * wnd_rescan - Scan all bitmap. Used while initialization.
 */
static int wnd_rescan(struct wnd_bitmap *wnd)
{ … }

int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits)
{ … }

/*
 * wnd_map - Call sb_bread for requested window.
 */
static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw)
{ … }

/*
 * wnd_set_free - Mark the bits range from bit to bit + bits as free.
 */
int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits)
{ … }

/*
 * wnd_set_used - Mark the bits range from bit to bit + bits as used.
 */
int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits)
{ … }

/*
 * wnd_set_used_safe - Mark the bits range from bit to bit + bits as used.
 *
 * Unlikely wnd_set_used/wnd_set_free this function is not full trusted.
 * It scans every bit in bitmap and marks free bit as used.
 * @done - how many bits were marked as used.
 *
 * NOTE: normally *done should be 0.
 */
int wnd_set_used_safe(struct wnd_bitmap *wnd, size_t bit, size_t bits,
		      size_t *done)
{ … }

/*
 * wnd_is_free_hlp
 *
 * Return: True if all clusters [bit, bit+bits) are free (bitmap only).
 */
static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits)
{ … }

/*
 * wnd_is_free
 *
 * Return: True if all clusters [bit, bit+bits) are free.
 */
bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits)
{ … }

/*
 * wnd_is_used
 *
 * Return: True if all clusters [bit, bit+bits) are used.
 */
bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits)
{ … }

/*
 * wnd_find - Look for free space.
 *
 * - flags - BITMAP_FIND_XXX flags
 *
 * Return: 0 if not found.
 */
size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint,
		size_t flags, size_t *allocated)
{ … }

/*
 * wnd_extend - Extend bitmap ($MFT bitmap).
 */
int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits)
{ … }

void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len)
{ … }

int ntfs_trim_fs(struct ntfs_sb_info *sbi, struct fstrim_range *range)
{ … }

#if BITS_PER_LONG == 64
bitmap_ulong;
#define cpu_to_ul(x) …
#define ul_to_cpu(x) …
#else
typedef __le32 bitmap_ulong;
#define cpu_to_ul …
#define ul_to_cpu …
#endif

void ntfs_bitmap_set_le(void *map, unsigned int start, int len)
{ … }

void ntfs_bitmap_clear_le(void *map, unsigned int start, int len)
{ … }

unsigned int ntfs_bitmap_weight_le(const void *bitmap, int bits)
{ … }