L4Re/departure

Annotated libext2fs/lib/libsupport/quotaio_tree.c

212:c0651b3b711f
181:49d8e9637cdb
2021-10-09 Paul Boddie file changeset files shortlog Updated libext2fs to version 1.46.2, also introducing some notes about the process of adapting the library for L4Re, together with a tool to generate a configuration from an existing, external "host" build of the library.
paul@181 1 
/*
paul@181 2 
 * Implementation of new quotafile format
paul@181 3 
 *
paul@181 4 
 * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
paul@181 5 
 */
paul@181 6 
 
 paul@181      7 
#include "config.h"
 
 paul@181      8 
#include <sys/types.h>
 
 paul@181      9 
#include <errno.h>
 
 paul@181     10 
#include <stdio.h>
 
 paul@181     11 
#include <stdlib.h>
 
 paul@181     12 
#include <string.h>
 
 paul@181     13 
#include <unistd.h>
 
 paul@181     14 
 
 paul@181     15 
#include "common.h"
 
 paul@181     16 
#include "quotaio_tree.h"
 
 paul@181     17 
#include "quotaio.h"
 
 paul@181     18 
 
 paul@181     19 
typedef char *dqbuf_t;
 
 paul@181     20 
 
 paul@181     21 
#define freedqbuf(buf)		ext2fs_free_mem(&buf)
 
 paul@181     22 
 
 paul@181     23 
static inline dqbuf_t getdqbuf(void)
 
 paul@181     24 
{
 
 paul@181     25 
	dqbuf_t buf;
 
 paul@181     26 
	if (ext2fs_get_memzero(QT_BLKSIZE, &buf)) {
 
 paul@181     27 
		log_err("Failed to allocate dqbuf");
 
 paul@181     28 
		return NULL;
 
 paul@181     29 
	}
 
 paul@181     30 
 
 paul@181     31 
	return buf;
 
 paul@181     32 
}
 
 paul@181     33 
 
 paul@181     34 
/* Is given dquot empty? */
 
 paul@181     35 
int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
 
 paul@181     36 
{
 
 paul@181     37 
	unsigned int i;
 
 paul@181     38 
 
 paul@181     39 
	for (i = 0; i < info->dqi_entry_size; i++)
 
 paul@181     40 
		if (disk[i])
 
 paul@181     41 
			return 0;
 
 paul@181     42 
	return 1;
 
 paul@181     43 
}
 
 paul@181     44 
 
 paul@181     45 
int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
 
 paul@181     46 
{
 
 paul@181     47 
	return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) /
 
 paul@181     48 
		info->dqi_entry_size;
 
 paul@181     49 
}
 
 paul@181     50 
 
 paul@181     51 
static int get_index(qid_t id, int depth)
 
 paul@181     52 
{
 
 paul@181     53 
	return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff;
 
 paul@181     54 
}
 
 paul@181     55 
 
 paul@181     56 
static inline void mark_quotafile_info_dirty(struct quota_handle *h)
 
 paul@181     57 
{
 
 paul@181     58 
	h->qh_io_flags |= IOFL_INFODIRTY;
 
 paul@181     59 
}
 
 paul@181     60 
 
 paul@181     61 
/* Read given block */
 
 paul@181     62 
static void read_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
 
 paul@181     63 
{
 
 paul@181     64 
	int err;
 
 paul@181     65 
 
 paul@181     66 
	err = h->e2fs_read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
 
 paul@181     67 
			QT_BLKSIZE);
 
 paul@181     68 
	if (err < 0)
 
 paul@181     69 
		log_err("Cannot read block %u: %s", blk, strerror(errno));
 
 paul@181     70 
	else if (err != QT_BLKSIZE)
 
 paul@181     71 
		memset(buf + err, 0, QT_BLKSIZE - err);
 
 paul@181     72 
}
 
 paul@181     73 
 
 paul@181     74 
/* Write block */
 
 paul@181     75 
static int write_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
 
 paul@181     76 
{
 
 paul@181     77 
	int err;
 
 paul@181     78 
 
 paul@181     79 
	err = h->e2fs_write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
 
 paul@181     80 
			QT_BLKSIZE);
 
 paul@181     81 
	if (err < 0 && errno != ENOSPC)
 
 paul@181     82 
		log_err("Cannot write block (%u): %s", blk, strerror(errno));
 
 paul@181     83 
	if (err != QT_BLKSIZE)
 
 paul@181     84 
		return -ENOSPC;
 
 paul@181     85 
	return 0;
 
 paul@181     86 
}
 
 paul@181     87 
 
 paul@181     88 
/* Get free block in file (either from free list or create new one) */
 
 paul@181     89 
static int get_free_dqblk(struct quota_handle *h)
 
 paul@181     90 
{
 
 paul@181     91 
	dqbuf_t buf = getdqbuf();
 
 paul@181     92 
	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181     93 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181     94 
	int blk;
 
 paul@181     95 
 
 paul@181     96 
	if (!buf)
 
 paul@181     97 
		return -ENOMEM;
 
 paul@181     98 
 
 paul@181     99 
	if (info->dqi_free_blk) {
 
 paul@181    100 
		blk = info->dqi_free_blk;
 
 paul@181    101 
		read_blk(h, blk, buf);
 
 paul@181    102 
		info->dqi_free_blk = ext2fs_le32_to_cpu(dh->dqdh_next_free);
 
 paul@181    103 
	} else {
 
 paul@181    104 
		memset(buf, 0, QT_BLKSIZE);
 
 paul@181    105 
		/* Assure block allocation... */
 
 paul@181    106 
		if (write_blk(h, info->dqi_blocks, buf) < 0) {
 
 paul@181    107 
			freedqbuf(buf);
 
 paul@181    108 
			log_err("Cannot allocate new quota block "
 
 paul@181    109 
				"(out of disk space).");
 
 paul@181    110 
			return -ENOSPC;
 
 paul@181    111 
		}
 
 paul@181    112 
		blk = info->dqi_blocks++;
 
 paul@181    113 
	}
 
 paul@181    114 
	mark_quotafile_info_dirty(h);
 
 paul@181    115 
	freedqbuf(buf);
 
 paul@181    116 
	return blk;
 
 paul@181    117 
}
 
 paul@181    118 
 
 paul@181    119 
/* Put given block to free list */
 
 paul@181    120 
static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf,
 
 paul@181    121 
			   unsigned int blk)
 
 paul@181    122 
{
 
 paul@181    123 
	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    124 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    125 
 
 paul@181    126 
	dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_blk);
 
 paul@181    127 
	dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 
 paul@181    128 
	dh->dqdh_entries = ext2fs_cpu_to_le16(0);
 
 paul@181    129 
	info->dqi_free_blk = blk;
 
 paul@181    130 
	mark_quotafile_info_dirty(h);
 
 paul@181    131 
	write_blk(h, blk, buf);
 
 paul@181    132 
}
 
 paul@181    133 
 
 paul@181    134 
/* Remove given block from the list of blocks with free entries */
 
 paul@181    135 
static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf,
 
 paul@181    136 
				unsigned int blk)
 
 paul@181    137 
{
 
 paul@181    138 
	dqbuf_t tmpbuf = getdqbuf();
 
 paul@181    139 
	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    140 
	unsigned int nextblk = ext2fs_le32_to_cpu(dh->dqdh_next_free), prevblk =
 
 paul@181    141 
 
 paul@181    142 
		ext2fs_le32_to_cpu(dh->dqdh_prev_free);
 
 paul@181    143 
 
 paul@181    144 
	if (!tmpbuf)
 
 paul@181    145 
		return;
 
 paul@181    146 
 
 paul@181    147 
	if (nextblk) {
 
 paul@181    148 
		read_blk(h, nextblk, tmpbuf);
 
 paul@181    149 
		((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 
 paul@181    150 
				dh->dqdh_prev_free;
 
 paul@181    151 
		write_blk(h, nextblk, tmpbuf);
 
 paul@181    152 
	}
 
 paul@181    153 
	if (prevblk) {
 
 paul@181    154 
		read_blk(h, prevblk, tmpbuf);
 
 paul@181    155 
		((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
 
 paul@181    156 
				dh->dqdh_next_free;
 
 paul@181    157 
		write_blk(h, prevblk, tmpbuf);
 
 paul@181    158 
	} else {
 
 paul@181    159 
		h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk;
 
 paul@181    160 
		mark_quotafile_info_dirty(h);
 
 paul@181    161 
	}
 
 paul@181    162 
	freedqbuf(tmpbuf);
 
 paul@181    163 
	dh->dqdh_next_free = dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 
 paul@181    164 
	write_blk(h, blk, buf);	/* No matter whether write succeeds
 
 paul@181    165 
				 * block is out of list */
 
 paul@181    166 
}
 
 paul@181    167 
 
 paul@181    168 
/* Insert given block to the beginning of list with free entries */
 
 paul@181    169 
static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf,
 
 paul@181    170 
				unsigned int blk)
 
 paul@181    171 
{
 
 paul@181    172 
	dqbuf_t tmpbuf = getdqbuf();
 
 paul@181    173 
	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    174 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    175 
 
 paul@181    176 
	if (!tmpbuf)
 
 paul@181    177 
		return;
 
 paul@181    178 
 
 paul@181    179 
	dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_entry);
 
 paul@181    180 
	dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 
 paul@181    181 
	write_blk(h, blk, buf);
 
 paul@181    182 
	if (info->dqi_free_entry) {
 
 paul@181    183 
		read_blk(h, info->dqi_free_entry, tmpbuf);
 
 paul@181    184 
		((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 
 paul@181    185 
				ext2fs_cpu_to_le32(blk);
 
 paul@181    186 
		write_blk(h, info->dqi_free_entry, tmpbuf);
 
 paul@181    187 
	}
 
 paul@181    188 
	freedqbuf(tmpbuf);
 
 paul@181    189 
	info->dqi_free_entry = blk;
 
 paul@181    190 
	mark_quotafile_info_dirty(h);
 
 paul@181    191 
}
 
 paul@181    192 
 
 paul@181    193 
/* Find space for dquot */
 
 paul@181    194 
static unsigned int find_free_dqentry(struct quota_handle *h,
 
 paul@181    195 
				      struct dquot *dquot, int *err)
 
 paul@181    196 
{
 
 paul@181    197 
	int blk, i;
 
 paul@181    198 
	struct qt_disk_dqdbheader *dh;
 
 paul@181    199 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    200 
	char *ddquot;
 
 paul@181    201 
	dqbuf_t buf;
 
 paul@181    202 
 
 paul@181    203 
	*err = 0;
 
 paul@181    204 
	buf = getdqbuf();
 
 paul@181    205 
	if (!buf) {
 
 paul@181    206 
		*err = -ENOMEM;
 
 paul@181    207 
		return 0;
 
 paul@181    208 
	}
 
 paul@181    209 
 
 paul@181    210 
	dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    211 
	if (info->dqi_free_entry) {
 
 paul@181    212 
		blk = info->dqi_free_entry;
 
 paul@181    213 
		read_blk(h, blk, buf);
 
 paul@181    214 
	} else {
 
 paul@181    215 
		blk = get_free_dqblk(h);
 
 paul@181    216 
		if (blk < 0) {
 
 paul@181    217 
			freedqbuf(buf);
 
 paul@181    218 
			*err = blk;
 
 paul@181    219 
			return 0;
 
 paul@181    220 
		}
 
 paul@181    221 
		memset(buf, 0, QT_BLKSIZE);
 
 paul@181    222 
		info->dqi_free_entry = blk;
 
 paul@181    223 
		mark_quotafile_info_dirty(h);
 
 paul@181    224 
	}
 
 paul@181    225 
 
 paul@181    226 
	/* Block will be full? */
 
 paul@181    227 
	if (ext2fs_le16_to_cpu(dh->dqdh_entries) + 1 >=
 
 paul@181    228 
	    qtree_dqstr_in_blk(info))
 
 paul@181    229 
		remove_free_dqentry(h, buf, blk);
 
 paul@181    230 
 
 paul@181    231 
	dh->dqdh_entries =
 
 paul@181    232 
		ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) + 1);
 
 paul@181    233 
	/* Find free structure in block */
 
 paul@181    234 
	ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 
 paul@181    235 
	for (i = 0;
 
 paul@181    236 
	     i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot);
 
 paul@181    237 
	     i++)
 
 paul@181    238 
		ddquot += info->dqi_entry_size;
 
 paul@181    239 
 
 paul@181    240 
	if (i == qtree_dqstr_in_blk(info))
 
 paul@181    241 
		log_err("find_free_dqentry(): Data block full unexpectedly.");
 
 paul@181    242 
 
 paul@181    243 
	write_blk(h, blk, buf);
 
 paul@181    244 
	dquot->dq_dqb.u.v2_mdqb.dqb_off =
 
 paul@181    245 
		(blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
 
 paul@181    246 
		i * info->dqi_entry_size;
 
 paul@181    247 
	freedqbuf(buf);
 
 paul@181    248 
	return blk;
 
 paul@181    249 
}
 
 paul@181    250 
 
 paul@181    251 
/* Insert reference to structure into the trie */
 
 paul@181    252 
static int do_insert_tree(struct quota_handle *h, struct dquot *dquot,
 
 paul@181    253 
			  unsigned int * treeblk, int depth)
 
 paul@181    254 
{
 
 paul@181    255 
	dqbuf_t buf;
 
 paul@181    256 
	int newson = 0, newact = 0;
 
 paul@181    257 
	__le32 *ref;
 
 paul@181    258 
	unsigned int newblk;
 
 paul@181    259 
	int ret = 0;
 
 paul@181    260 
 
 paul@181    261 
	log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth);
 
 paul@181    262 
	buf = getdqbuf();
 
 paul@181    263 
	if (!buf)
 
 paul@181    264 
		return -ENOMEM;
 
 paul@181    265 
 
 paul@181    266 
	if (!*treeblk) {
 
 paul@181    267 
		ret = get_free_dqblk(h);
 
 paul@181    268 
		if (ret < 0)
 
 paul@181    269 
			goto out_buf;
 
 paul@181    270 
		*treeblk = ret;
 
 paul@181    271 
		memset(buf, 0, QT_BLKSIZE);
 
 paul@181    272 
		newact = 1;
 
 paul@181    273 
	} else {
 
 paul@181    274 
		read_blk(h, *treeblk, buf);
 
 paul@181    275 
	}
 
 paul@181    276 
 
 paul@181    277 
	ref = (__le32 *) buf;
 
 paul@181    278 
	newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 
 paul@181    279 
	if (!newblk)
 
 paul@181    280 
		newson = 1;
 
 paul@181    281 
	if (depth == QT_TREEDEPTH - 1) {
 
 paul@181    282 
		if (newblk)
 
 paul@181    283 
			log_err("Inserting already present quota entry "
 
 paul@181    284 
				"(block %u).",
 
 paul@181    285 
				ref[get_index(dquot->dq_id, depth)]);
 
 paul@181    286 
		newblk = find_free_dqentry(h, dquot, &ret);
 
 paul@181    287 
	} else {
 
 paul@181    288 
		ret = do_insert_tree(h, dquot, &newblk, depth + 1);
 
 paul@181    289 
	}
 
 paul@181    290 
 
 paul@181    291 
	if (newson && ret >= 0) {
 
 paul@181    292 
		ref[get_index(dquot->dq_id, depth)] =
 
 paul@181    293 
			ext2fs_cpu_to_le32(newblk);
 
 paul@181    294 
		write_blk(h, *treeblk, buf);
 
 paul@181    295 
	} else if (newact && ret < 0) {
 
 paul@181    296 
		put_free_dqblk(h, buf, *treeblk);
 
 paul@181    297 
	}
 
 paul@181    298 
 
 paul@181    299 
out_buf:
 
 paul@181    300 
	freedqbuf(buf);
 
 paul@181    301 
	return ret;
 
 paul@181    302 
}
 
 paul@181    303 
 
 paul@181    304 
/* Wrapper for inserting quota structure into tree */
 
 paul@181    305 
static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot)
 
 paul@181    306 
{
 
 paul@181    307 
	unsigned int tmp = QT_TREEOFF;
 
 paul@181    308 
 
 paul@181    309 
	if (do_insert_tree(h, dquot, &tmp, 0) < 0)
 
 paul@181    310 
		log_err("Cannot write quota (id %u): %s",
 
 paul@181    311 
			(unsigned int) dquot->dq_id, strerror(errno));
 
 paul@181    312 
}
 
 paul@181    313 
 
 paul@181    314 
/* Write dquot to file */
 
 paul@181    315 
void qtree_write_dquot(struct dquot *dquot)
 
 paul@181    316 
{
 
 paul@181    317 
	errcode_t retval;
 
 paul@181    318 
	unsigned int ret;
 
 paul@181    319 
	char *ddquot;
 
 paul@181    320 
	struct quota_handle *h = dquot->dq_h;
 
 paul@181    321 
	struct qtree_mem_dqinfo *info =
 
 paul@181    322 
			&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    323 
	log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u",
 
 paul@181    324 
			dquot->dq_dqb.u.v2_mdqb.dqb_off,
 
 paul@181    325 
			info->dqi_entry_size);
 
 paul@181    326 
	retval = ext2fs_get_mem(info->dqi_entry_size, &ddquot);
 
 paul@181    327 
	if (retval) {
 
 paul@181    328 
		errno = ENOMEM;
 
 paul@181    329 
		log_err("Quota write failed (id %u): %s",
 
 paul@181    330 
			(unsigned int)dquot->dq_id, strerror(errno));
 
 paul@181    331 
		return;
 
 paul@181    332 
	}
 
 paul@181    333 
	memset(ddquot, 0, info->dqi_entry_size);
 
 paul@181    334 
 
 paul@181    335 
	if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)
 
 paul@181    336 
		dq_insert_tree(dquot->dq_h, dquot);
 
 paul@181    337 
	info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
 
 paul@181    338 
	log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u",
 
 paul@181    339 
			dquot->dq_dqb.u.v2_mdqb.dqb_off,
 
 paul@181    340 
			info->dqi_entry_size);
 
 paul@181    341 
	ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot,
 
 paul@181    342 
			info->dqi_entry_size);
 
 paul@181    343 
 
 paul@181    344 
	if (ret != info->dqi_entry_size) {
 
 paul@181    345 
		if (ret > 0)
 
 paul@181    346 
			errno = ENOSPC;
 
 paul@181    347 
		log_err("Quota write failed (id %u): %s",
 
 paul@181    348 
			(unsigned int)dquot->dq_id, strerror(errno));
 
 paul@181    349 
	}
 
 paul@181    350 
	ext2fs_free_mem(&ddquot);
 
 paul@181    351 
}
 
 paul@181    352 
 
 paul@181    353 
/* Free dquot entry in data block */
 
 paul@181    354 
static void free_dqentry(struct quota_handle *h, struct dquot *dquot,
 
 paul@181    355 
			 unsigned int blk)
 
 paul@181    356 
{
 
 paul@181    357 
	struct qt_disk_dqdbheader *dh;
 
 paul@181    358 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    359 
	dqbuf_t buf = getdqbuf();
 
 paul@181    360 
 
 paul@181    361 
	if (!buf)
 
 paul@181    362 
		return;
 
 paul@181    363 
 
 paul@181    364 
	if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk)
 
 paul@181    365 
		log_err("Quota structure has offset to other block (%u) "
 
 paul@181    366 
			"than it should (%u).", blk,
 
 paul@181    367 
			  (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >>
 
 paul@181    368 
				  QT_BLKSIZE_BITS));
 
 paul@181    369 
 
 paul@181    370 
	read_blk(h, blk, buf);
 
 paul@181    371 
	dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    372 
	dh->dqdh_entries =
 
 paul@181    373 
		ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) - 1);
 
 paul@181    374 
 
 paul@181    375 
	if (!ext2fs_le16_to_cpu(dh->dqdh_entries)) {	/* Block got free? */
 
 paul@181    376 
		remove_free_dqentry(h, buf, blk);
 
 paul@181    377 
		put_free_dqblk(h, buf, blk);
 
 paul@181    378 
	} else {
 
 paul@181    379 
		memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off &
 
 paul@181    380 
			      ((1 << QT_BLKSIZE_BITS) - 1)),
 
 paul@181    381 
		       0, info->dqi_entry_size);
 
 paul@181    382 
 
 paul@181    383 
		/* First free entry? */
 
 paul@181    384 
		if (ext2fs_le16_to_cpu(dh->dqdh_entries) ==
 
 paul@181    385 
				qtree_dqstr_in_blk(info) - 1)
 
 paul@181    386 
			/* This will also write data block */
 
 paul@181    387 
			insert_free_dqentry(h, buf, blk);
 
 paul@181    388 
		else
 
 paul@181    389 
			write_blk(h, blk, buf);
 
 paul@181    390 
	}
 
 paul@181    391 
	dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 
 paul@181    392 
	freedqbuf(buf);
 
 paul@181    393 
}
 
 paul@181    394 
 
 paul@181    395 
/* Remove reference to dquot from tree */
 
 paul@181    396 
static void remove_tree(struct quota_handle *h, struct dquot *dquot,
 
 paul@181    397 
			unsigned int * blk, int depth)
 
 paul@181    398 
{
 
 paul@181    399 
	dqbuf_t buf = getdqbuf();
 
 paul@181    400 
	unsigned int newblk;
 
 paul@181    401 
	__le32 *ref = (__le32 *) buf;
 
 paul@181    402 
 
 paul@181    403 
	if (!buf)
 
 paul@181    404 
		return;
 
 paul@181    405 
 
 paul@181    406 
	read_blk(h, *blk, buf);
 
 paul@181    407 
	newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 
 paul@181    408 
	if (depth == QT_TREEDEPTH - 1) {
 
 paul@181    409 
		free_dqentry(h, dquot, newblk);
 
 paul@181    410 
		newblk = 0;
 
 paul@181    411 
	} else {
 
 paul@181    412 
		remove_tree(h, dquot, &newblk, depth + 1);
 
 paul@181    413 
	}
 
 paul@181    414 
 
 paul@181    415 
	if (!newblk) {
 
 paul@181    416 
		int i;
 
 paul@181    417 
 
 paul@181    418 
		ref[get_index(dquot->dq_id, depth)] = ext2fs_cpu_to_le32(0);
 
 paul@181    419 
 
 paul@181    420 
		/* Block got empty? */
 
 paul@181    421 
		for (i = 0; i < QT_BLKSIZE && !buf[i]; i++);
 
 paul@181    422 
 
 paul@181    423 
		/* Don't put the root block into the free block list */
 
 paul@181    424 
		if (i == QT_BLKSIZE && *blk != QT_TREEOFF) {
 
 paul@181    425 
			put_free_dqblk(h, buf, *blk);
 
 paul@181    426 
			*blk = 0;
 
 paul@181    427 
		} else {
 
 paul@181    428 
			write_blk(h, *blk, buf);
 
 paul@181    429 
		}
 
 paul@181    430 
	}
 
 paul@181    431 
	freedqbuf(buf);
 
 paul@181    432 
}
 
 paul@181    433 
 
 paul@181    434 
/* Delete dquot from tree */
 
 paul@181    435 
void qtree_delete_dquot(struct dquot *dquot)
 
 paul@181    436 
{
 
 paul@181    437 
	unsigned int tmp = QT_TREEOFF;
 
 paul@181    438 
 
 paul@181    439 
	if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)	/* Even not allocated? */
 
 paul@181    440 
		return;
 
 paul@181    441 
	remove_tree(dquot->dq_h, dquot, &tmp, 0);
 
 paul@181    442 
}
 
 paul@181    443 
 
 paul@181    444 
/* Find entry in block */
 
 paul@181    445 
static ext2_loff_t find_block_dqentry(struct quota_handle *h,
 
 paul@181    446 
				      struct dquot *dquot, unsigned int blk)
 
 paul@181    447 
{
 
 paul@181    448 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    449 
	dqbuf_t buf = getdqbuf();
 
 paul@181    450 
	int i;
 
 paul@181    451 
	char *ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 
 paul@181    452 
 
 paul@181    453 
	if (!buf)
 
 paul@181    454 
		return -ENOMEM;
 
 paul@181    455 
 
 paul@181    456 
	read_blk(h, blk, buf);
 
 paul@181    457 
	for (i = 0;
 
 paul@181    458 
	     i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot);
 
 paul@181    459 
	     i++)
 
 paul@181    460 
		ddquot += info->dqi_entry_size;
 
 paul@181    461 
 
 paul@181    462 
	if (i == qtree_dqstr_in_blk(info))
 
 paul@181    463 
		log_err("Quota for id %u referenced but not present.",
 
 paul@181    464 
			dquot->dq_id);
 
 paul@181    465 
	freedqbuf(buf);
 
 paul@181    466 
	return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
 
 paul@181    467 
		i * info->dqi_entry_size;
 
 paul@181    468 
}
 
 paul@181    469 
 
 paul@181    470 
/* Find entry for given id in the tree */
 
 paul@181    471 
static ext2_loff_t find_tree_dqentry(struct quota_handle *h,
 
 paul@181    472 
				     struct dquot *dquot,
 
 paul@181    473 
				     unsigned int blk, int depth)
 
 paul@181    474 
{
 
 paul@181    475 
	dqbuf_t buf = getdqbuf();
 
 paul@181    476 
	ext2_loff_t ret = 0;
 
 paul@181    477 
	__le32 *ref = (__le32 *) buf;
 
 paul@181    478 
 
 paul@181    479 
	if (!buf)
 
 paul@181    480 
		return -ENOMEM;
 
 paul@181    481 
 
 paul@181    482 
	read_blk(h, blk, buf);
 
 paul@181    483 
	ret = 0;
 
 paul@181    484 
	blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 
 paul@181    485 
	if (!blk)	/* No reference? */
 
 paul@181    486 
		goto out_buf;
 
 paul@181    487 
	if (depth < QT_TREEDEPTH - 1)
 
 paul@181    488 
		ret = find_tree_dqentry(h, dquot, blk, depth + 1);
 
 paul@181    489 
	else
 
 paul@181    490 
		ret = find_block_dqentry(h, dquot, blk);
 
 paul@181    491 
out_buf:
 
 paul@181    492 
	freedqbuf(buf);
 
 paul@181    493 
	return ret;
 
 paul@181    494 
}
 
 paul@181    495 
 
 paul@181    496 
/* Find entry for given id in the tree - wrapper function */
 
 paul@181    497 
static inline ext2_loff_t find_dqentry(struct quota_handle *h,
 
 paul@181    498 
				       struct dquot *dquot)
 
 paul@181    499 
{
 
 paul@181    500 
	return find_tree_dqentry(h, dquot, QT_TREEOFF, 0);
 
 paul@181    501 
}
 
 paul@181    502 
 
 paul@181    503 
/*
 
 paul@181    504 
 *  Read dquot from disk.
 
 paul@181    505 
 */
 
 paul@181    506 
struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id)
 
 paul@181    507 
{
 
 paul@181    508 
	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    509 
	ext2_loff_t offset;
 
 paul@181    510 
	unsigned int ret;
 
 paul@181    511 
	char *ddquot;
 
 paul@181    512 
	struct dquot *dquot = get_empty_dquot();
 
 paul@181    513 
 
 paul@181    514 
	if (!dquot)
 
 paul@181    515 
		return NULL;
 
 paul@181    516 
	if (ext2fs_get_mem(info->dqi_entry_size, &ddquot)) {
 
 paul@181    517 
		ext2fs_free_mem(&dquot);
 
 paul@181    518 
		return NULL;
 
 paul@181    519 
	}
 
 paul@181    520 
 
 paul@181    521 
	dquot->dq_id = id;
 
 paul@181    522 
	dquot->dq_h = h;
 
 paul@181    523 
	dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 
 paul@181    524 
	memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk));
 
 paul@181    525 
 
 paul@181    526 
	offset = find_dqentry(h, dquot);
 
 paul@181    527 
	if (offset > 0) {
 
 paul@181    528 
		dquot->dq_dqb.u.v2_mdqb.dqb_off = offset;
 
 paul@181    529 
		ret = h->e2fs_read(&h->qh_qf, offset, ddquot,
 
 paul@181    530 
			info->dqi_entry_size);
 
 paul@181    531 
		if (ret != info->dqi_entry_size) {
 
 paul@181    532 
			if (ret > 0)
 
 paul@181    533 
				errno = EIO;
 
 paul@181    534 
			log_err("Cannot read quota structure for id %u: %s",
 
 paul@181    535 
				dquot->dq_id, strerror(errno));
 
 paul@181    536 
		}
 
 paul@181    537 
		info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
 
 paul@181    538 
	}
 
 paul@181    539 
	ext2fs_free_mem(&ddquot);
 
 paul@181    540 
	return dquot;
 
 paul@181    541 
}
 
 paul@181    542 
 
 paul@212    543 
static int check_reference(struct quota_handle *h, unsigned int blk)
 
 paul@212    544 
{
 
 paul@212    545 
	if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) {
 
 paul@212    546 
		log_err("Illegal reference (%u >= %u) in %s quota file",
 
 paul@212    547 
			blk, h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
 
 paul@212    548 
			quota_type2name(h->qh_type));
 
 paul@212    549 
		return -1;
 
 paul@212    550 
	}
 
 paul@212    551 
	return 0;
 
 paul@212    552 
}
 
 paul@212    553 
 
 paul@181    554 
/*
 
 paul@181    555 
 * Scan all dquots in file and call callback on each
 
 paul@181    556 
 */
 
 paul@181    557 
#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
 
 paul@181    558 
#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
 
 paul@181    559 
 
 paul@181    560 
static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
 
 paul@181    561 
			int (*process_dquot) (struct dquot *, void *),
 
 paul@181    562 
			void *data)
 
 paul@181    563 
{
 
 paul@181    564 
	struct qtree_mem_dqinfo *info =
 
 paul@181    565 
			&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 
 paul@181    566 
	dqbuf_t buf = getdqbuf();
 
 paul@181    567 
	struct qt_disk_dqdbheader *dh;
 
 paul@181    568 
	char *ddata;
 
 paul@181    569 
	int entries, i;
 
 paul@181    570 
 
 paul@181    571 
	if (!buf)
 
 paul@212    572 
		return -1;
 
 paul@181    573 
 
 paul@181    574 
	set_bit(bitmap, blk);
 
 paul@181    575 
	read_blk(dquot->dq_h, blk, buf);
 
 paul@181    576 
	dh = (struct qt_disk_dqdbheader *)buf;
 
 paul@181    577 
	ddata = buf + sizeof(struct qt_disk_dqdbheader);
 
 paul@181    578 
	entries = ext2fs_le16_to_cpu(dh->dqdh_entries);
 
 paul@181    579 
	for (i = 0; i < qtree_dqstr_in_blk(info);
 
 paul@181    580 
			i++, ddata += info->dqi_entry_size)
 
 paul@181    581 
		if (!qtree_entry_unused(info, ddata)) {
 
 paul@181    582 
			dquot->dq_dqb.u.v2_mdqb.dqb_off =
 
 paul@181    583 
				(blk << QT_BLKSIZE_BITS) +
 
 paul@181    584 
				sizeof(struct qt_disk_dqdbheader) +
 
 paul@181    585 
				i * info->dqi_entry_size;
 
 paul@181    586 
			info->dqi_ops->disk2mem_dqblk(dquot, ddata);
 
 paul@181    587 
			if (process_dquot(dquot, data) < 0)
 
 paul@181    588 
				break;
 
 paul@181    589 
		}
 
 paul@181    590 
	freedqbuf(buf);
 
 paul@181    591 
	return entries;
 
 paul@181    592 
}
 
 paul@181    593 
 
 paul@181    594 
static int report_tree(struct dquot *dquot, unsigned int blk, int depth,
 
 paul@181    595 
		       char *bitmap,
 
 paul@181    596 
		       int (*process_dquot) (struct dquot *, void *),
 
 paul@181    597 
		       void *data)
 
 paul@181    598 
{
 
 paul@212    599 
	int entries = 0, ret, i;
 
 paul@181    600 
	dqbuf_t buf = getdqbuf();
 
 paul@181    601 
	__le32 *ref = (__le32 *) buf;
 
 paul@181    602 
 
 paul@181    603 
	if (!buf)
 
 paul@181    604 
		return 0;
 
 paul@181    605 
 
 paul@181    606 
	read_blk(dquot->dq_h, blk, buf);
 
 paul@181    607 
	if (depth == QT_TREEDEPTH - 1) {
 
 paul@181    608 
		for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 
 paul@181    609 
			blk = ext2fs_le32_to_cpu(ref[i]);
 
 paul@212    610 
			if (check_reference(dquot->dq_h, blk)) {
 
 paul@212    611 
				entries = -1;
 
 paul@212    612 
				goto errout;
 
 paul@212    613 
			}
 
 paul@212    614 
			if (blk && !get_bit(bitmap, blk)) {
 
 paul@212    615 
				ret = report_block(dquot, blk, bitmap,
 
 paul@212    616 
						   process_dquot, data);
 
 paul@212    617 
				if (ret < 0) {
 
 paul@212    618 
					entries = ret;
 
 paul@212    619 
					goto errout;
 
 paul@212    620 
				}
 
 paul@212    621 
				entries += ret;
 
 paul@212    622 
			}
 
 paul@181    623 
		}
 
 paul@181    624 
	} else {
 
 paul@181    625 
		for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 
 paul@181    626 
			blk = ext2fs_le32_to_cpu(ref[i]);
 
 paul@181    627 
			if (blk) {
 
 paul@212    628 
				if (check_reference(dquot->dq_h, blk)) {
 
 paul@212    629 
					entries = -1;
 
 paul@212    630 
					goto errout;
 
 paul@212    631 
				}
 
 paul@212    632 
				ret = report_tree(dquot, blk, depth + 1,
 
 paul@212    633 
						  bitmap, process_dquot,
 
 paul@212    634 
						  data);
 
 paul@212    635 
				if (ret < 0) {
 
 paul@212    636 
					entries = ret;
 
 paul@212    637 
					goto errout;
 
 paul@212    638 
				}
 
 paul@212    639 
				entries += ret;
 
 paul@181    640 
			}
 
 paul@181    641 
		}
 
 paul@181    642 
	}
 
 paul@212    643 
errout:
 
 paul@181    644 
	freedqbuf(buf);
 
 paul@181    645 
	return entries;
 
 paul@181    646 
}
 
 paul@181    647 
 
 paul@181    648 
static unsigned int find_set_bits(char *bmp, int blocks)
 
 paul@181    649 
{
 
 paul@181    650 
	unsigned int	used = 0;
 
 paul@181    651 
	int		i;
 
 paul@181    652 
 
 paul@181    653 
	for (i = 0; i < blocks; i++)
 
 paul@181    654 
		if (get_bit(bmp, i))
 
 paul@181    655 
			used++;
 
 paul@181    656 
	return used;
 
 paul@181    657 
}
 
 paul@181    658 
 
 paul@181    659 
int qtree_scan_dquots(struct quota_handle *h,
 
 paul@181    660 
		      int (*process_dquot) (struct dquot *, void *),
 
 paul@181    661 
		      void *data)
 
 paul@181    662 
{
 
 paul@212    663 
	int ret;
 
 paul@181    664 
	char *bitmap;
 
 paul@181    665 
	struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
 
 paul@181    666 
	struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
 
 paul@181    667 
	struct dquot *dquot = get_empty_dquot();
 
 paul@181    668 
 
 paul@181    669 
	if (!dquot)
 
 paul@181    670 
		return -1;
 
 paul@181    671 
 
 paul@181    672 
	dquot->dq_h = h;
 
 paul@181    673 
	if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) {
 
 paul@181    674 
		ext2fs_free_mem(&dquot);
 
 paul@181    675 
		return -1;
 
 paul@181    676 
	}
 
 paul@212    677 
	ret = report_tree(dquot, QT_TREEOFF, 0, bitmap, process_dquot, data);
 
 paul@212    678 
	if (ret < 0)
 
 paul@212    679 
		goto errout;
 
 paul@212    680 
	v2info->dqi_used_entries = ret;
 
 paul@181    681 
	v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
 
 paul@212    682 
	ret = 0;
 
 paul@212    683 
errout:
 
 paul@181    684 
	ext2fs_free_mem(&bitmap);
 
 paul@181    685 
	ext2fs_free_mem(&dquot);
 
 paul@212    686 
	return ret;
 
 paul@181    687 
}