[deliverable/linux.git] / fs / reiserfs / objectid.c

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

#include <linux/string.h>
#include <linux/random.h>
#include <linux/time.h>
#include "reiserfs.h"

/* find where objectid map starts */
#define objectid_map(s,rs) (old_format_only (s) ? \
                         (__le32 *)((struct reiserfs_super_block_v1 *)(rs) + 1) :\
			 (__le32 *)((rs) + 1))

#ifdef CONFIG_REISERFS_CHECK

static void check_objectid_map(struct super_block *s, __le32 * map)
{
	if (le32_to_cpu(map[0]) != 1)
		reiserfs_panic(s, "vs-15010", "map corrupted: %lx",
			       (long unsigned int)le32_to_cpu(map[0]));

	/* FIXME: add something else here */
}

#else
static void check_objectid_map(struct super_block *s, __le32 * map)
{;
}
#endif

/*
 * When we allocate objectids we allocate the first unused objectid.
 * Each sequence of objectids in use (the odd sequences) is followed
 * by a sequence of objectids not in use (the even sequences).  We
 * only need to record the last objectid in each of these sequences
 * (both the odd and even sequences) in order to fully define the
 * boundaries of the sequences.  A consequence of allocating the first
 * objectid not in use is that under most conditions this scheme is
 * extremely compact.  The exception is immediately after a sequence
 * of operations which deletes a large number of objects of
 * non-sequential objectids, and even then it will become compact
 * again as soon as more objects are created.  Note that many
 * interesting optimizations of layout could result from complicating
 * objectid assignment, but we have deferred making them for now.
 */

/* get unique object identifier */
__u32 reiserfs_get_unused_objectid(struct reiserfs_transaction_handle *th)
{
	struct super_block *s = th->t_super;
	struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
	__le32 *map = objectid_map(s, rs);
	__u32 unused_objectid;

	BUG_ON(!th->t_trans_id);

	check_objectid_map(s, map);

	reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
	/* comment needed -Hans */
	unused_objectid = le32_to_cpu(map[1]);
	if (unused_objectid == U32_MAX) {
		reiserfs_warning(s, "reiserfs-15100", "no more object ids");
		reiserfs_restore_prepared_buffer(s, SB_BUFFER_WITH_SB(s));
		return 0;
	}

	/*
	 * This incrementation allocates the first unused objectid. That
	 * is to say, the first entry on the objectid map is the first
	 * unused objectid, and by incrementing it we use it.  See below
	 * where we check to see if we eliminated a sequence of unused
	 * objectids....
	 */
	map[1] = cpu_to_le32(unused_objectid + 1);

	/*
	 * Now we check to see if we eliminated the last remaining member of
	 * the first even sequence (and can eliminate the sequence by
	 * eliminating its last objectid from oids), and can collapse the
	 * first two odd sequences into one sequence.  If so, then the net
	 * result is to eliminate a pair of objectids from oids.  We do this
	 * by shifting the entire map to the left.
	 */
	if (sb_oid_cursize(rs) > 2 && map[1] == map[2]) {
		memmove(map + 1, map + 3,
			(sb_oid_cursize(rs) - 3) * sizeof(__u32));
		set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
	}

	journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
	return unused_objectid;
}

/* makes object identifier unused */
void reiserfs_release_objectid(struct reiserfs_transaction_handle *th,
			       __u32 objectid_to_release)
{
	struct super_block *s = th->t_super;
	struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
	__le32 *map = objectid_map(s, rs);
	int i = 0;

	BUG_ON(!th->t_trans_id);
	/*return; */
	check_objectid_map(s, map);

	reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
	journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));

	/*
	 * start at the beginning of the objectid map (i = 0) and go to
	 * the end of it (i = disk_sb->s_oid_cursize).  Linear search is
	 * what we use, though it is possible that binary search would be
	 * more efficient after performing lots of deletions (which is
	 * when oids is large.)  We only check even i's.
	 */
	while (i < sb_oid_cursize(rs)) {
		if (objectid_to_release == le32_to_cpu(map[i])) {
			/* This incrementation unallocates the objectid. */
			le32_add_cpu(&map[i], 1);

			/*
			 * Did we unallocate the last member of an
			 * odd sequence, and can shrink oids?
			 */
			if (map[i] == map[i + 1]) {
				/* shrink objectid map */
				memmove(map + i, map + i + 2,
					(sb_oid_cursize(rs) - i -
					 2) * sizeof(__u32));
				set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);

				RFALSE(sb_oid_cursize(rs) < 2 ||
				       sb_oid_cursize(rs) > sb_oid_maxsize(rs),
				       "vs-15005: objectid map corrupted cur_size == %d (max == %d)",
				       sb_oid_cursize(rs), sb_oid_maxsize(rs));
			}
			return;
		}

		if (objectid_to_release > le32_to_cpu(map[i]) &&
		    objectid_to_release < le32_to_cpu(map[i + 1])) {
			/* size of objectid map is not changed */
			if (objectid_to_release + 1 == le32_to_cpu(map[i + 1])) {
				le32_add_cpu(&map[i + 1], -1);
				return;
			}

			/*
			 * JDM comparing two little-endian values for
			 * equality -- safe
			 */
			/*
			 * objectid map must be expanded, but
			 * there is no space
			 */
			if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
				PROC_INFO_INC(s, leaked_oid);
				return;
			}

			/* expand the objectid map */
			memmove(map + i + 3, map + i + 1,
				(sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
			map[i + 1] = cpu_to_le32(objectid_to_release);
			map[i + 2] = cpu_to_le32(objectid_to_release + 1);
			set_sb_oid_cursize(rs, sb_oid_cursize(rs) + 2);
			return;
		}
		i += 2;
	}

	reiserfs_error(s, "vs-15011", "tried to free free object id (%lu)",
		       (long unsigned)objectid_to_release);
}

int reiserfs_convert_objectid_map_v1(struct super_block *s)
{
	struct reiserfs_super_block *disk_sb = SB_DISK_SUPER_BLOCK(s);
	int cur_size = sb_oid_cursize(disk_sb);
	int new_size = (s->s_blocksize - SB_SIZE) / sizeof(__u32) / 2 * 2;
	int old_max = sb_oid_maxsize(disk_sb);
	struct reiserfs_super_block_v1 *disk_sb_v1;
	__le32 *objectid_map, *new_objectid_map;
	int i;

	disk_sb_v1 =
	    (struct reiserfs_super_block_v1 *)(SB_BUFFER_WITH_SB(s)->b_data);
	objectid_map = (__le32 *) (disk_sb_v1 + 1);
	new_objectid_map = (__le32 *) (disk_sb + 1);

	if (cur_size > new_size) {
		/*
		 * mark everyone used that was listed as free at
		 * the end of the objectid map
		 */
		objectid_map[new_size - 1] = objectid_map[cur_size - 1];
		set_sb_oid_cursize(disk_sb, new_size);
	}
	/* move the smaller objectid map past the end of the new super */
	for (i = new_size - 1; i >= 0; i--) {
		objectid_map[i + (old_max - new_size)] = objectid_map[i];
	}

	/* set the max size so we don't overflow later */
	set_sb_oid_maxsize(disk_sb, new_size);

	/* Zero out label and generate random UUID */
	memset(disk_sb->s_label, 0, sizeof(disk_sb->s_label));
	generate_random_uuid(disk_sb->s_uuid);

	/* finally, zero out the unused chunk of the new super */
	memset(disk_sb->s_unused, 0, sizeof(disk_sb->s_unused));
	return 0;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
	3	*/
	4
1da177e4 LT	5	#include <linux/string.h>
	6	#include <linux/random.h>
	7	#include <linux/time.h>
f466c6fd	8	#include "reiserfs.h"
1da177e4	9
098297b2	10	/* find where objectid map starts */
1da177e4	11	#define objectid_map(s,rs) (old_format_only (s) ? \
3e8962be AV	12	(__le32 )((struct reiserfs_super_block_v1 )(rs) + 1) :\
3e8962be AV	13	(__le32 *)((rs) + 1))
1da177e4	14
1da177e4 LT	15	#ifdef CONFIG_REISERFS_CHECK
1da177e4 LT	16
bd4c625c	17	static void check_objectid_map(struct super_block s, __le32 map)
1da177e4	18	{
bd4c625c	19	if (le32_to_cpu(map[0]) != 1)
c3a9c210	20	reiserfs_panic(s, "vs-15010", "map corrupted: %lx",
bd4c625c	21	(long unsigned int)le32_to_cpu(map[0]));
1da177e4	22
098297b2	23	/* FIXME: add something else here */
1da177e4 LT	24	}
	25
	26	#else
bd4c625c LT	27	static void check_objectid_map(struct super_block s, __le32 map)
	28	{;
	29	}
1da177e4 LT	30	#endif
1da177e4 LT	31
098297b2 JM	32	/*
	33	* When we allocate objectids we allocate the first unused objectid.
	34	* Each sequence of objectids in use (the odd sequences) is followed
	35	* by a sequence of objectids not in use (the even sequences). We
	36	* only need to record the last objectid in each of these sequences
	37	* (both the odd and even sequences) in order to fully define the
	38	* boundaries of the sequences. A consequence of allocating the first
	39	* objectid not in use is that under most conditions this scheme is
	40	* extremely compact. The exception is immediately after a sequence
	41	* of operations which deletes a large number of objects of
	42	* non-sequential objectids, and even then it will become compact
	43	* again as soon as more objects are created. Note that many
	44	* interesting optimizations of layout could result from complicating
	45	* objectid assignment, but we have deferred making them for now.
	46	*/
1da177e4	47
1da177e4	48	/* get unique object identifier */
bd4c625c	49	__u32 reiserfs_get_unused_objectid(struct reiserfs_transaction_handle *th)
1da177e4	50	{
bd4c625c LT	51	struct super_block *s = th->t_super;
	52	struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
	53	__le32 *map = objectid_map(s, rs);
	54	__u32 unused_objectid;
	55
	56	BUG_ON(!th->t_trans_id);
	57
	58	check_objectid_map(s, map);
	59
	60	reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
	61	/* comment needed -Hans */
	62	unused_objectid = le32_to_cpu(map[1]);
	63	if (unused_objectid == U32_MAX) {
45b03d5e	64	reiserfs_warning(s, "reiserfs-15100", "no more object ids");
bd4c625c LT	65	reiserfs_restore_prepared_buffer(s, SB_BUFFER_WITH_SB(s));
	66	return 0;
	67	}
1da177e4	68
098297b2 JM	69	/*
	70	* This incrementation allocates the first unused objectid. That
	71	* is to say, the first entry on the objectid map is the first
	72	* unused objectid, and by incrementing it we use it. See below
	73	* where we check to see if we eliminated a sequence of unused
	74	* objectids....
	75	*/
bd4c625c LT	76	map[1] = cpu_to_le32(unused_objectid + 1);
bd4c625c LT	77
098297b2 JM	78	/*
	79	* Now we check to see if we eliminated the last remaining member of
	80	* the first even sequence (and can eliminate the sequence by
	81	* eliminating its last objectid from oids), and can collapse the
	82	* first two odd sequences into one sequence. If so, then the net
	83	* result is to eliminate a pair of objectids from oids. We do this
	84	* by shifting the entire map to the left.
	85	*/
bd4c625c LT	86	if (sb_oid_cursize(rs) > 2 && map[1] == map[2]) {
	87	memmove(map + 1, map + 3,
	88	(sb_oid_cursize(rs) - 3) * sizeof(__u32));
	89	set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
	90	}
1da177e4	91
09f1b80b	92	journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
bd4c625c	93	return unused_objectid;
1da177e4 LT	94	}
1da177e4 LT	95
1da177e4	96	/* makes object identifier unused */
bd4c625c LT	97	void reiserfs_release_objectid(struct reiserfs_transaction_handle *th,
bd4c625c LT	98	__u32 objectid_to_release)
1da177e4	99	{
bd4c625c LT	100	struct super_block *s = th->t_super;
	101	struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
	102	__le32 *map = objectid_map(s, rs);
	103	int i = 0;
	104
	105	BUG_ON(!th->t_trans_id);
098297b2	106	/return; /
bd4c625c LT	107	check_objectid_map(s, map);
	108
	109	reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
09f1b80b	110	journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
bd4c625c	111
098297b2 JM	112	/*
	113	* start at the beginning of the objectid map (i = 0) and go to
	114	* the end of it (i = disk_sb->s_oid_cursize). Linear search is
	115	* what we use, though it is possible that binary search would be
	116	* more efficient after performing lots of deletions (which is
	117	* when oids is large.) We only check even i's.
	118	*/
bd4c625c LT	119	while (i < sb_oid_cursize(rs)) {
	120	if (objectid_to_release == le32_to_cpu(map[i])) {
	121	/* This incrementation unallocates the objectid. */
9e902df6	122	le32_add_cpu(&map[i], 1);
bd4c625c	123
098297b2 JM	124	/*
	125	* Did we unallocate the last member of an
	126	* odd sequence, and can shrink oids?
	127	*/
bd4c625c LT	128	if (map[i] == map[i + 1]) {
	129	/* shrink objectid map */
	130	memmove(map + i, map + i + 2,
	131	(sb_oid_cursize(rs) - i -
	132	2) * sizeof(__u32));
bd4c625c LT	133	set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
	134
	135	RFALSE(sb_oid_cursize(rs) < 2 \|\|
	136	sb_oid_cursize(rs) > sb_oid_maxsize(rs),
	137	"vs-15005: objectid map corrupted cur_size == %d (max == %d)",
	138	sb_oid_cursize(rs), sb_oid_maxsize(rs));
	139	}
	140	return;
	141	}
	142
	143	if (objectid_to_release > le32_to_cpu(map[i]) &&
	144	objectid_to_release < le32_to_cpu(map[i + 1])) {
	145	/* size of objectid map is not changed */
	146	if (objectid_to_release + 1 == le32_to_cpu(map[i + 1])) {
9e902df6	147	le32_add_cpu(&map[i + 1], -1);
bd4c625c LT	148	return;
	149	}
	150
098297b2 JM	151	/*
	152	* JDM comparing two little-endian values for
	153	* equality -- safe
	154	*/
	155	/*
	156	* objectid map must be expanded, but
	157	* there is no space
	158	*/
bd4c625c	159	if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
bd4c625c LT	160	PROC_INFO_INC(s, leaked_oid);
	161	return;
	162	}
	163
	164	/* expand the objectid map */
	165	memmove(map + i + 3, map + i + 1,
	166	(sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
	167	map[i + 1] = cpu_to_le32(objectid_to_release);
	168	map[i + 2] = cpu_to_le32(objectid_to_release + 1);
	169	set_sb_oid_cursize(rs, sb_oid_cursize(rs) + 2);
	170	return;
	171	}
	172	i += 2;
1da177e4 LT	173	}
1da177e4 LT	174
0030b645 JM	175	reiserfs_error(s, "vs-15011", "tried to free free object id (%lu)",
0030b645 JM	176	(long unsigned)objectid_to_release);
bd4c625c	177	}
1da177e4	178
bd4c625c LT	179	int reiserfs_convert_objectid_map_v1(struct super_block *s)
	180	{
	181	struct reiserfs_super_block *disk_sb = SB_DISK_SUPER_BLOCK(s);
	182	int cur_size = sb_oid_cursize(disk_sb);
	183	int new_size = (s->s_blocksize - SB_SIZE) / sizeof(__u32) / 2 * 2;
	184	int old_max = sb_oid_maxsize(disk_sb);
	185	struct reiserfs_super_block_v1 *disk_sb_v1;
	186	__le32 objectid_map, new_objectid_map;
	187	int i;
	188
	189	disk_sb_v1 =
	190	(struct reiserfs_super_block_v1 *)(SB_BUFFER_WITH_SB(s)->b_data);
	191	objectid_map = (__le32 *) (disk_sb_v1 + 1);
	192	new_objectid_map = (__le32 *) (disk_sb + 1);
	193
	194	if (cur_size > new_size) {
098297b2 JM	195	/*
	196	* mark everyone used that was listed as free at
	197	* the end of the objectid map
bd4c625c LT	198	*/
	199	objectid_map[new_size - 1] = objectid_map[cur_size - 1];
	200	set_sb_oid_cursize(disk_sb, new_size);
	201	}
	202	/* move the smaller objectid map past the end of the new super */
	203	for (i = new_size - 1; i >= 0; i--) {
	204	objectid_map[i + (old_max - new_size)] = objectid_map[i];
1da177e4	205	}
1da177e4	206
bd4c625c LT	207	/* set the max size so we don't overflow later */
bd4c625c LT	208	set_sb_oid_maxsize(disk_sb, new_size);
1da177e4	209
bd4c625c LT	210	/* Zero out label and generate random UUID */
	211	memset(disk_sb->s_label, 0, sizeof(disk_sb->s_label));
	212	generate_random_uuid(disk_sb->s_uuid);
1da177e4	213
bd4c625c LT	214	/* finally, zero out the unused chunk of the new super */
	215	memset(disk_sb->s_unused, 0, sizeof(disk_sb->s_unused));
	216	return 0;
1da177e4	217	}