linux/fs/ntfs3/index.c

// SPDX-License-Identifier: GPL-2.0
/*
 *
 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
 *
 */

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

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

static const struct INDEX_NAMES { … } s_index_names[INDEX_MUTEX_TOTAL] = …;

/*
 * cmp_fnames - Compare two names in index.
 *
 * if l1 != 0
 *   Both names are little endian on-disk ATTR_FILE_NAME structs.
 * else
 *   key1 - cpu_str, key2 - ATTR_FILE_NAME
 */
static int cmp_fnames(const void *key1, size_t l1, const void *key2, size_t l2,
		      const void *data)
{ … }

/*
 * cmp_uint - $SII of $Secure and $Q of Quota
 */
static int cmp_uint(const void *key1, size_t l1, const void *key2, size_t l2,
		    const void *data)
{ … }

/*
 * cmp_sdh - $SDH of $Secure
 */
static int cmp_sdh(const void *key1, size_t l1, const void *key2, size_t l2,
		   const void *data)
{ … }

/*
 * cmp_uints - $O of ObjId and "$R" for Reparse.
 */
static int cmp_uints(const void *key1, size_t l1, const void *key2, size_t l2,
		     const void *data)
{ … }

static inline NTFS_CMP_FUNC get_cmp_func(const struct INDEX_ROOT *root)
{ … }

struct bmp_buf { … };

static int bmp_buf_get(struct ntfs_index *indx, struct ntfs_inode *ni,
		       size_t bit, struct bmp_buf *bbuf)
{ … }

static void bmp_buf_put(struct bmp_buf *bbuf, bool dirty)
{ … }

/*
 * indx_mark_used - Mark the bit @bit as used.
 */
static int indx_mark_used(struct ntfs_index *indx, struct ntfs_inode *ni,
			  size_t bit)
{ … }

/*
 * indx_mark_free - Mark the bit @bit as free.
 */
static int indx_mark_free(struct ntfs_index *indx, struct ntfs_inode *ni,
			  size_t bit)
{ … }

/*
 * scan_nres_bitmap
 *
 * If ntfs_readdir calls this function (indx_used_bit -> scan_nres_bitmap),
 * inode is shared locked and no ni_lock.
 * Use rw_semaphore for read/write access to bitmap_run.
 */
static int scan_nres_bitmap(struct ntfs_inode *ni, struct ATTRIB *bitmap,
			    struct ntfs_index *indx, size_t from,
			    bool (*fn)(const ulong *buf, u32 bit, u32 bits,
				       size_t *ret),
			    size_t *ret)
{ … }

static bool scan_for_free(const ulong *buf, u32 bit, u32 bits, size_t *ret)
{ … }

/*
 * indx_find_free - Look for free bit.
 *
 * Return: -1 if no free bits.
 */
static int indx_find_free(struct ntfs_index *indx, struct ntfs_inode *ni,
			  size_t *bit, struct ATTRIB **bitmap)
{ … }

static bool scan_for_used(const ulong *buf, u32 bit, u32 bits, size_t *ret)
{ … }

/*
 * indx_used_bit - Look for used bit.
 *
 * Return: MINUS_ONE_T if no used bits.
 */
int indx_used_bit(struct ntfs_index *indx, struct ntfs_inode *ni, size_t *bit)
{ … }

/*
 * hdr_find_split
 *
 * Find a point at which the index allocation buffer would like to be split.
 * NOTE: This function should never return 'END' entry NULL returns on error.
 */
static const struct NTFS_DE *hdr_find_split(const struct INDEX_HDR *hdr)
{ … }

/*
 * hdr_insert_head - Insert some entries at the beginning of the buffer.
 *
 * It is used to insert entries into a newly-created buffer.
 */
static const struct NTFS_DE *hdr_insert_head(struct INDEX_HDR *hdr,
					     const void *ins, u32 ins_bytes)
{ … }

/*
 * index_hdr_check
 *
 * return true if INDEX_HDR is valid
 */
static bool index_hdr_check(const struct INDEX_HDR *hdr, u32 bytes)
{ … }

/*
 * index_buf_check
 *
 * return true if INDEX_BUFFER seems is valid
 */
static bool index_buf_check(const struct INDEX_BUFFER *ib, u32 bytes,
			    const CLST *vbn)
{ … }

void fnd_clear(struct ntfs_fnd *fnd)
{ … }

static int fnd_push(struct ntfs_fnd *fnd, struct indx_node *n,
		    struct NTFS_DE *e)
{ … }

static struct indx_node *fnd_pop(struct ntfs_fnd *fnd)
{ … }

static bool fnd_is_empty(struct ntfs_fnd *fnd)
{ … }

/*
 * hdr_find_e - Locate an entry the index buffer.
 *
 * If no matching entry is found, it returns the first entry which is greater
 * than the desired entry If the search key is greater than all the entries the
 * buffer, it returns the 'end' entry. This function does a binary search of the
 * current index buffer, for the first entry that is <= to the search value.
 *
 * Return: NULL if error.
 */
static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
				  const struct INDEX_HDR *hdr, const void *key,
				  size_t key_len, const void *ctx, int *diff)
{ … }

/*
 * hdr_insert_de - Insert an index entry into the buffer.
 *
 * 'before' should be a pointer previously returned from hdr_find_e.
 */
static struct NTFS_DE *hdr_insert_de(const struct ntfs_index *indx,
				     struct INDEX_HDR *hdr,
				     const struct NTFS_DE *de,
				     struct NTFS_DE *before, const void *ctx)
{ … }

/*
 * hdr_delete_de - Remove an entry from the index buffer.
 */
static inline struct NTFS_DE *hdr_delete_de(struct INDEX_HDR *hdr,
					    struct NTFS_DE *re)
{ … }

void indx_clear(struct ntfs_index *indx)
{ … }

int indx_init(struct ntfs_index *indx, struct ntfs_sb_info *sbi,
	      const struct ATTRIB *attr, enum index_mutex_classed type)
{ … }

static struct indx_node *indx_new(struct ntfs_index *indx,
				  struct ntfs_inode *ni, CLST vbn,
				  const __le64 *sub_vbn)
{ … }

struct INDEX_ROOT *indx_get_root(struct ntfs_index *indx, struct ntfs_inode *ni,
				 struct ATTRIB **attr, struct mft_inode **mi)
{ … }

static int indx_write(struct ntfs_index *indx, struct ntfs_inode *ni,
		      struct indx_node *node, int sync)
{ … }

/*
 * indx_read
 *
 * If ntfs_readdir calls this function
 * inode is shared locked and no ni_lock.
 * Use rw_semaphore for read/write access to alloc_run.
 */
int indx_read(struct ntfs_index *indx, struct ntfs_inode *ni, CLST vbn,
	      struct indx_node **node)
{ … }

/*
 * indx_find - Scan NTFS directory for given entry.
 */
int indx_find(struct ntfs_index *indx, struct ntfs_inode *ni,
	      const struct INDEX_ROOT *root, const void *key, size_t key_len,
	      const void *ctx, int *diff, struct NTFS_DE **entry,
	      struct ntfs_fnd *fnd)
{ … }

int indx_find_sort(struct ntfs_index *indx, struct ntfs_inode *ni,
		   const struct INDEX_ROOT *root, struct NTFS_DE **entry,
		   struct ntfs_fnd *fnd)
{ … }

int indx_find_raw(struct ntfs_index *indx, struct ntfs_inode *ni,
		  const struct INDEX_ROOT *root, struct NTFS_DE **entry,
		  size_t *off, struct ntfs_fnd *fnd)
{ … }

/*
 * indx_create_allocate - Create "Allocation + Bitmap" attributes.
 */
static int indx_create_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
				CLST *vbn)
{ … }

/*
 * indx_add_allocate - Add clusters to index.
 */
static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
			     CLST *vbn)
{ … }

/*
 * indx_insert_into_root - Attempt to insert an entry into the index root.
 *
 * @undo - True if we undoing previous remove.
 * If necessary, it will twiddle the index b-tree.
 */
static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
				 const struct NTFS_DE *new_de,
				 struct NTFS_DE *root_de, const void *ctx,
				 struct ntfs_fnd *fnd, bool undo)
{ … }

/*
 * indx_insert_into_buffer
 *
 * Attempt to insert an entry into an Index Allocation Buffer.
 * If necessary, it will split the buffer.
 */
static int
indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni,
			struct INDEX_ROOT *root, const struct NTFS_DE *new_de,
			const void *ctx, int level, struct ntfs_fnd *fnd)
{ … }

/*
 * indx_insert_entry - Insert new entry into index.
 *
 * @undo - True if we undoing previous remove.
 */
int indx_insert_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
		      const struct NTFS_DE *new_de, const void *ctx,
		      struct ntfs_fnd *fnd, bool undo)
{ … }

/*
 * indx_find_buffer - Locate a buffer from the tree.
 */
static struct indx_node *indx_find_buffer(struct ntfs_index *indx,
					  struct ntfs_inode *ni,
					  const struct INDEX_ROOT *root,
					  __le64 vbn, struct indx_node *n)
{ … }

/*
 * indx_shrink - Deallocate unused tail indexes.
 */
static int indx_shrink(struct ntfs_index *indx, struct ntfs_inode *ni,
		       size_t bit)
{ … }

static int indx_free_children(struct ntfs_index *indx, struct ntfs_inode *ni,
			      const struct NTFS_DE *e, bool trim)
{ … }

/*
 * indx_get_entry_to_replace
 *
 * Find a replacement entry for a deleted entry.
 * Always returns a node entry:
 * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
 */
static int indx_get_entry_to_replace(struct ntfs_index *indx,
				     struct ntfs_inode *ni,
				     const struct NTFS_DE *de_next,
				     struct NTFS_DE **de_to_replace,
				     struct ntfs_fnd *fnd)
{ … }

/*
 * indx_delete_entry - Delete an entry from the index.
 */
int indx_delete_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
		      const void *key, u32 key_len, const void *ctx)
{ … }

/*
 * Update duplicated information in directory entry
 * 'dup' - info from MFT record
 */
int indx_update_dup(struct ntfs_inode *ni, struct ntfs_sb_info *sbi,
		    const struct ATTR_FILE_NAME *fname,
		    const struct NTFS_DUP_INFO *dup, int sync)
{ … }