bmap.h 8.55 KB
Newer Older
1
/* SPDX-License-Identifier: GPL-2.0+ */
Koji Sato's avatar
Koji Sato committed
2
/*
3
 * NILFS block mapping.
Koji Sato's avatar
Koji Sato committed
4 5 6
 *
 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
 *
7
 * Written by Koji Sato.
Koji Sato's avatar
Koji Sato committed
8 9 10 11 12 13 14 15
 */

#ifndef _NILFS_BMAP_H
#define _NILFS_BMAP_H

#include <linux/types.h>
#include <linux/fs.h>
#include <linux/buffer_head.h>
16
#include <linux/nilfs2_ondisk.h>	/* nilfs_binfo, nilfs_inode, etc */
Koji Sato's avatar
Koji Sato committed
17
#include "alloc.h"
18
#include "dat.h"
Koji Sato's avatar
Koji Sato committed
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#define NILFS_BMAP_INVALID_PTR	0

#define nilfs_bmap_keydiff_abs(diff)	((diff) < 0 ? -(diff) : (diff))


struct nilfs_bmap;

/**
 * union nilfs_bmap_ptr_req - request for bmap ptr
 * @bpr_ptr: bmap pointer
 * @bpr_req: request for persistent allocator
 */
union nilfs_bmap_ptr_req {
	__u64 bpr_ptr;
	struct nilfs_palloc_req bpr_req;
};

/**
 * struct nilfs_bmap_stats - bmap statistics
 * @bs_nblocks: number of blocks created or deleted
 */
struct nilfs_bmap_stats {
	unsigned int bs_nblocks;
};

/**
 * struct nilfs_bmap_operations - bmap operation table
47 48 49 50 51 52 53 54 55 56 57 58 59
 * @bop_lookup:               single block search operation
 * @bop_lookup_contig:        consecutive block search operation
 * @bop_insert:               block insertion operation
 * @bop_delete:               block delete operation
 * @bop_clear:                block mapping resource release operation
 * @bop_propagate:            operation to propagate dirty state towards the
 *                            mapping root
 * @bop_lookup_dirty_buffers: operation to collect dirty block buffers
 * @bop_assign:               disk block address assignment operation
 * @bop_mark:                 operation to mark in-use blocks as dirty for
 *                            relocation by GC
 * @bop_seek_key:             find valid block key operation
 * @bop_last_key:             find last valid block key operation
Koji Sato's avatar
Koji Sato committed
60 61 62
 */
struct nilfs_bmap_operations {
	int (*bop_lookup)(const struct nilfs_bmap *, __u64, int, __u64 *);
63
	int (*bop_lookup_contig)(const struct nilfs_bmap *, __u64, __u64 *,
64
				 unsigned int);
Koji Sato's avatar
Koji Sato committed
65 66 67 68
	int (*bop_insert)(struct nilfs_bmap *, __u64, __u64);
	int (*bop_delete)(struct nilfs_bmap *, __u64);
	void (*bop_clear)(struct nilfs_bmap *);

69
	int (*bop_propagate)(struct nilfs_bmap *, struct buffer_head *);
Koji Sato's avatar
Koji Sato committed
70 71 72 73 74 75 76 77 78
	void (*bop_lookup_dirty_buffers)(struct nilfs_bmap *,
					 struct list_head *);

	int (*bop_assign)(struct nilfs_bmap *,
			  struct buffer_head **,
			  sector_t,
			  union nilfs_binfo *);
	int (*bop_mark)(struct nilfs_bmap *, __u64, int);

79
	int (*bop_seek_key)(const struct nilfs_bmap *, __u64, __u64 *);
Koji Sato's avatar
Koji Sato committed
80
	int (*bop_last_key)(const struct nilfs_bmap *, __u64 *);
81

82
	/* private: internal use only */
Koji Sato's avatar
Koji Sato committed
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
	int (*bop_check_insert)(const struct nilfs_bmap *, __u64);
	int (*bop_check_delete)(struct nilfs_bmap *, __u64);
	int (*bop_gather_data)(struct nilfs_bmap *, __u64 *, __u64 *, int);
};


#define NILFS_BMAP_SIZE		(NILFS_INODE_BMAP_SIZE * sizeof(__le64))
#define NILFS_BMAP_KEY_BIT	(sizeof(unsigned long) * 8 /* CHAR_BIT */)
#define NILFS_BMAP_NEW_PTR_INIT	\
	(1UL << (sizeof(unsigned long) * 8 /* CHAR_BIT */ - 1))

static inline int nilfs_bmap_is_new_ptr(unsigned long ptr)
{
	return !!(ptr & NILFS_BMAP_NEW_PTR_INIT);
}


/**
 * struct nilfs_bmap - bmap structure
 * @b_u: raw data
 * @b_sem: semaphore
 * @b_inode: owner of bmap
 * @b_ops: bmap operation table
 * @b_last_allocated_key: last allocated key for data block
 * @b_last_allocated_ptr: last allocated ptr for data block
108
 * @b_ptr_type: pointer type
Koji Sato's avatar
Koji Sato committed
109
 * @b_state: state
110
 * @b_nchildren_per_block: maximum number of child nodes for non-root nodes
Koji Sato's avatar
Koji Sato committed
111 112 113 114 115 116 117 118 119 120 121
 */
struct nilfs_bmap {
	union {
		__u8 u_flags;
		__le64 u_data[NILFS_BMAP_SIZE / sizeof(__le64)];
	} b_u;
	struct rw_semaphore b_sem;
	struct inode *b_inode;
	const struct nilfs_bmap_operations *b_ops;
	__u64 b_last_allocated_key;
	__u64 b_last_allocated_ptr;
122
	int b_ptr_type;
Koji Sato's avatar
Koji Sato committed
123
	int b_state;
124
	__u16 b_nchildren_per_block;
Koji Sato's avatar
Koji Sato committed
125 126
};

127 128
/* pointer type */
#define NILFS_BMAP_PTR_P	0	/* physical block number (i.e. LBN) */
129 130 131 132 133 134 135 136
#define NILFS_BMAP_PTR_VS	1	/*
					 * virtual block number (single
					 * version)
					 */
#define NILFS_BMAP_PTR_VM	2	/*
					 * virtual block number (has multiple
					 * versions)
					 */
137 138 139 140
#define NILFS_BMAP_PTR_U	(-1)	/* never perform pointer operations */

#define NILFS_BMAP_USE_VBN(bmap)	((bmap)->b_ptr_type > 0)

Koji Sato's avatar
Koji Sato committed
141 142 143
/* state */
#define NILFS_BMAP_DIRTY	0x00000001

144 145 146 147 148 149 150
/**
 * struct nilfs_bmap_store - shadow copy of bmap state
 * @data: cached raw block mapping of on-disk inode
 * @last_allocated_key: cached value of last allocated key for data block
 * @last_allocated_ptr: cached value of last allocated ptr for data block
 * @state: cached value of state field of bmap structure
 */
151 152 153 154 155 156
struct nilfs_bmap_store {
	__le64 data[NILFS_BMAP_SIZE / sizeof(__le64)];
	__u64 last_allocated_key;
	__u64 last_allocated_ptr;
	int state;
};
Koji Sato's avatar
Koji Sato committed
157 158 159 160

int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *);
int nilfs_bmap_read(struct nilfs_bmap *, struct nilfs_inode *);
void nilfs_bmap_write(struct nilfs_bmap *, struct nilfs_inode *);
161
int nilfs_bmap_lookup_contig(struct nilfs_bmap *, __u64, __u64 *, unsigned int);
162 163
int nilfs_bmap_insert(struct nilfs_bmap *bmap, __u64 key, unsigned long rec);
int nilfs_bmap_delete(struct nilfs_bmap *bmap, __u64 key);
164
int nilfs_bmap_seek_key(struct nilfs_bmap *bmap, __u64 start, __u64 *keyp);
165 166
int nilfs_bmap_last_key(struct nilfs_bmap *bmap, __u64 *keyp);
int nilfs_bmap_truncate(struct nilfs_bmap *bmap, __u64 key);
Koji Sato's avatar
Koji Sato committed
167 168 169 170 171 172 173 174 175 176
void nilfs_bmap_clear(struct nilfs_bmap *);
int nilfs_bmap_propagate(struct nilfs_bmap *, struct buffer_head *);
void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *, struct list_head *);
int nilfs_bmap_assign(struct nilfs_bmap *, struct buffer_head **,
		      unsigned long, union nilfs_binfo *);
int nilfs_bmap_lookup_at_level(struct nilfs_bmap *, __u64, int, __u64 *);
int nilfs_bmap_mark(struct nilfs_bmap *, __u64, int);

void nilfs_bmap_init_gc(struct nilfs_bmap *);

177 178
void nilfs_bmap_save(const struct nilfs_bmap *, struct nilfs_bmap_store *);
void nilfs_bmap_restore(struct nilfs_bmap *, const struct nilfs_bmap_store *);
Koji Sato's avatar
Koji Sato committed
179

180 181 182 183 184 185
static inline int nilfs_bmap_lookup(struct nilfs_bmap *bmap, __u64 key,
				    __u64 *ptr)
{
	return nilfs_bmap_lookup_at_level(bmap, key, 1, ptr);
}

Koji Sato's avatar
Koji Sato committed
186 187 188
/*
 * Internal use only
 */
189
struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *);
190 191

static inline int nilfs_bmap_prepare_alloc_ptr(struct nilfs_bmap *bmap,
192 193
					       union nilfs_bmap_ptr_req *req,
					       struct inode *dat)
194
{
195 196
	if (dat)
		return nilfs_dat_prepare_alloc(dat, &req->bpr_req);
197 198 199 200 201 202
	/* ignore target ptr */
	req->bpr_ptr = bmap->b_last_allocated_ptr++;
	return 0;
}

static inline void nilfs_bmap_commit_alloc_ptr(struct nilfs_bmap *bmap,
203 204
					       union nilfs_bmap_ptr_req *req,
					       struct inode *dat)
205
{
206 207
	if (dat)
		nilfs_dat_commit_alloc(dat, &req->bpr_req);
208 209 210
}

static inline void nilfs_bmap_abort_alloc_ptr(struct nilfs_bmap *bmap,
211 212
					      union nilfs_bmap_ptr_req *req,
					      struct inode *dat)
213
{
214 215
	if (dat)
		nilfs_dat_abort_alloc(dat, &req->bpr_req);
216 217 218 219 220
	else
		bmap->b_last_allocated_ptr--;
}

static inline int nilfs_bmap_prepare_end_ptr(struct nilfs_bmap *bmap,
221 222
					     union nilfs_bmap_ptr_req *req,
					     struct inode *dat)
223
{
224
	return dat ? nilfs_dat_prepare_end(dat, &req->bpr_req) : 0;
225 226 227
}

static inline void nilfs_bmap_commit_end_ptr(struct nilfs_bmap *bmap,
228 229
					     union nilfs_bmap_ptr_req *req,
					     struct inode *dat)
230
{
231 232 233
	if (dat)
		nilfs_dat_commit_end(dat, &req->bpr_req,
				     bmap->b_ptr_type == NILFS_BMAP_PTR_VS);
234 235 236
}

static inline void nilfs_bmap_abort_end_ptr(struct nilfs_bmap *bmap,
237 238
					    union nilfs_bmap_ptr_req *req,
					    struct inode *dat)
239
{
240 241
	if (dat)
		nilfs_dat_abort_end(dat, &req->bpr_req);
242
}
Koji Sato's avatar
Koji Sato committed
243

244 245 246 247 248 249 250
static inline void nilfs_bmap_set_target_v(struct nilfs_bmap *bmap, __u64 key,
					   __u64 ptr)
{
	bmap->b_last_allocated_key = key;
	bmap->b_last_allocated_ptr = ptr;
}

Koji Sato's avatar
Koji Sato committed
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284
__u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *,
			      const struct buffer_head *);

__u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *, __u64);
__u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *);


/* Assume that bmap semaphore is locked. */
static inline int nilfs_bmap_dirty(const struct nilfs_bmap *bmap)
{
	return !!(bmap->b_state & NILFS_BMAP_DIRTY);
}

/* Assume that bmap semaphore is locked. */
static inline void nilfs_bmap_set_dirty(struct nilfs_bmap *bmap)
{
	bmap->b_state |= NILFS_BMAP_DIRTY;
}

/* Assume that bmap semaphore is locked. */
static inline void nilfs_bmap_clear_dirty(struct nilfs_bmap *bmap)
{
	bmap->b_state &= ~NILFS_BMAP_DIRTY;
}


#define NILFS_BMAP_LARGE	0x1

#define NILFS_BMAP_SMALL_LOW	NILFS_DIRECT_KEY_MIN
#define NILFS_BMAP_SMALL_HIGH	NILFS_DIRECT_KEY_MAX
#define NILFS_BMAP_LARGE_LOW	NILFS_BTREE_ROOT_NCHILDREN_MAX
#define NILFS_BMAP_LARGE_HIGH	NILFS_BTREE_KEY_MAX

#endif	/* _NILFS_BMAP_H */