FishEye: file PVFS/src/common/misc/dist-dir-utils.c

Annotated File View

shuangy	1.1.2.1	1	/*
		2	* (C) 2001 Clemson University and The University of Chicago
		3	*
		4	* See COPYING in top-level directory.
		5	*/
		6
		7	#include <stdio.h>
		8	#include <stdlib.h>
		9	#include <string.h>
		10	#include <math.h>
		11	#include <assert.h>
		12
		13	#include "dist-dir-utils.h"
		14	#include "md5.h"
		15
		16
		17	/****************************
		18	* helper functions
		19	* **************************/
		20
		21	/* calculate log2 of number */
		22	static double my_log2(const double n)
		23	{
shuangy	1.1.2.2	24	return log(n) / log(2.0);
shuangy	1.1.2.1	25	}
		26
		27	/* calculate branch_level for a server from a bitmap */
		28	static int dist_dir_calc_branch_level(
shuangy	1.1.2.2	29	const PVFS_dist_dir_attr *dist_dir_attr,
shuangy	1.1.2.2	30	const PVFS_dist_dir_bitmap bitmap)
shuangy	1.1.2.1	31	{
		32	int level = 0;
		33	int server_no, num_servers;
		34
		35	server_no = dist_dir_attr->server_no;
		36	num_servers = dist_dir_attr->num_servers;
		37
shuangy	1.1.2.2	38	/* meta handle copy (server_no = -1) shall not reach here */
shuangy	1.1.2.1	39	assert(server_no >= 0 && server_no < num_servers);
shuangy	1.1.2.2	40	assert(bitmap != NULL);
shuangy	1.1.2.1	41
shuangy	1.1.2.1	42	if(!(TST_BIT(bitmap, server_no)))
shuangy	1.1.2.2	43	{
shuangy	1.1.2.1	44	return -1; /* not an active server */
shuangy	1.1.2.2	45	}
shuangy	1.1.2.1	46
		47	/* get the number of bits above which all bits are zero */
		48	while( server_no >> level )
shuangy	1.1.2.2	49	{
shuangy	1.1.2.1	50	level++;
shuangy	1.1.2.2	51	}
shuangy	1.1.2.1	52
		53	/* until no splitting node is set */
		54	while( TST_BIT(bitmap, server_no + (1l << level)) )
shuangy	1.1.2.2	55	{
shuangy	1.1.2.1	56	level++;
shuangy	1.1.2.2	57	}
shuangy	1.1.2.1	58
		59	return level;
		60	}
		61
		62	/*****************************
		63	* main operation functions
		64	* ***************************/
		65
		66	/* init dir state function, set all parameters
shuangy	1.1.2.2	67	* server_no <- -1..(num_servers-1)
shuangy	1.1.2.1	68	* pre_dsg_num_server: pre-set a number of servers, used for known large directory. default value can be 1.
		69	*/
		70
		71	int PINT_init_dist_dir_state(
shuangy	1.1.2.2	72	PVFS_dist_dir_attr *dist_dir_attr,
		73	PVFS_dist_dir_bitmap *bitmap_ptr,
		74	const int num_servers,
		75	const int server_no,
		76	int pre_dsg_num_server)
shuangy	1.1.2.1	77	{
		78	int i;
		79
		80	assert(dist_dir_attr != NULL);
		81
shuangy	1.1.2.2	82	/* -1 <= server_no < num_servers && 0 < pre_dsg_num_server <= num_servers */
		83	assert( (num_servers < 1) \|\|
		84	(server_no < -1) \|\| /* metadata handle has server_no = -1 */
		85	(server_no >= num_servers));
		86
		87	if ((pre_dsg_num_server <= 0) \|\|
		88	(pre_dsg_num_server > num_servers))
		89	{
		90	pre_dsg_num_server = num_servers;
		91	}
shuangy	1.1.2.1	92
		93	dist_dir_attr->num_servers = num_servers;
		94	dist_dir_attr->server_no = server_no;
shuangy	1.1.2.2	95	/* tree_height start from 0 */
shuangy	1.1.2.2	96	dist_dir_attr->tree_height = (int)ceil(my_log2((double)num_servers));
shuangy	1.1.2.1	97
		98	/* increase bitmap_size if 2^tree_height > 32
		99	* bitmap has at least 2^tree_height bits, that is, the number of leaves of a full tree. */
		100	if( (1l << dist_dir_attr->tree_height) >
		101	(sizeof(PVFS_dist_dir_bitmap_basetype) * 8))
shuangy	1.1.2.2	102	{
shuangy	1.1.2.1	103	dist_dir_attr->bitmap_size = ((1l << dist_dir_attr->tree_height) >> 5);
shuangy	1.1.2.2	104	}
shuangy	1.1.2.1	105	else
shuangy	1.1.2.2	106	{
shuangy	1.1.2.1	107	dist_dir_attr->bitmap_size = 1;
shuangy	1.1.2.2	108	}
shuangy	1.1.2.1	109
		110	*bitmap_ptr = (PVFS_dist_dir_bitmap) malloc(
		111	dist_dir_attr->bitmap_size * sizeof(PVFS_dist_dir_bitmap_basetype));
		112	if ((*bitmap_ptr) == NULL)
shuangy	1.1.2.2	113	{
shuangy	1.1.2.1	114	return -1;
shuangy	1.1.2.2	115	}
shuangy	1.1.2.1	116
		117	memset((*bitmap_ptr), 0,
		118	dist_dir_attr->bitmap_size * sizeof(PVFS_dist_dir_bitmap_basetype));
		119
		120	for(i = pre_dsg_num_server-1; i >= 0; i--)
shuangy	1.1.2.2	121	{
shuangy	1.1.2.1	122	SET_BIT((*bitmap_ptr), i);
shuangy	1.1.2.2	123	}
shuangy	1.1.2.1	124
shuangy	1.1.2.2	125	if(server_no > -1) /* an dirdata server */
		126	{
		127	dist_dir_attr->branch_level = dist_dir_calc_branch_level(dist_dir_attr, *bitmap_ptr);
		128	}
		129	else /* a meta server */
		130	{
		131	dist_dir_attr->branch_level = -1;
		132	}
shuangy	1.1.2.1	133
		134	/* set split size */
		135	dist_dir_attr->split_size = PVFS_DIST_DIR_MAX_ENTRIES;
		136	return 0;
		137	}
		138
		139
		140	/*
		141	* client uses this function to find the server that should hold
		142	* a new dir entry, based on the current tree
		143	* hash can be any value, whose rightmost several bits will be examined.
		144	*/
		145	int PINT_find_dist_dir_bucket(
shuangy	1.1.2.2	146	const PVFS_dist_dir_hash_type hash,
		147	const PVFS_dist_dir_attr *const dist_dir_attr,
		148	const PVFS_dist_dir_bitmap bitmap)
shuangy	1.1.2.1	149	{
		150	PVFS_dist_dir_hash_type node_val;
		151	int level;
		152
		153	assert(dist_dir_attr != NULL);
shuangy	1.1.2.2	154	assert(bitmap != NULL);
shuangy	1.1.2.1	155
		156	level = dist_dir_attr->tree_height;
		157
		158	if(level < 0)
shuangy	1.1.2.2	159	{
shuangy	1.1.2.1	160	return -1;
shuangy	1.1.2.2	161	}
shuangy	1.1.2.1	162
		163	for( node_val = hash & ((1l << level) - 1); /* use the rightmost 'tree_height' bits */
		164	(level >= 0) && !(TST_BIT(bitmap, node_val)); /* test if node_val bit is set */
		165	node_val &= ((1l << (--level)) - 1) ); /* if it's not, use less bits of the hash value */
		166
		167	return (int)node_val; /* assume tree_height < 32 */
		168	}
		169
		170
		171	/*
		172	* this code return the index of the new node when a bucket is to be split
		173	*/
		174	int PINT_find_dist_dir_split_node(
shuangy	1.1.2.2	175	const PVFS_dist_dir_attr *const dist_dir_attr,
shuangy	1.1.2.2	176	const PVFS_dist_dir_bitmap bitmap)
shuangy	1.1.2.1	177	{
shuangy	1.1.2.1	178	int new_node_val;
shuangy	1.1.2.2	179	int branch_level;
shuangy	1.1.2.1	180
shuangy	1.1.2.2	181	assert((dist_dir_attr != NULL) &&
		182	(dist_dir_attr->server_no > -1) &&
		183	(bitmap != NULL));
		184
		185	branch_level = dist_dir_attr->branch_level;
		186
		187	/* meta server or inactive dirdata server should not come here */
		188	assert(branch_level > -1);
shuangy	1.1.2.1	189
shuangy	1.1.2.1	190	/* if it reaches the maximum tree height */
shuangy	1.1.2.2	191	if (branch_level >= dist_dir_attr->tree_height)
shuangy	1.1.2.2	192	{
shuangy	1.1.2.1	193	return -1;
shuangy	1.1.2.2	194	}
shuangy	1.1.2.1	195
shuangy	1.1.2.1	196	/* calculate new node value */
shuangy	1.1.2.2	197	new_node_val = dist_dir_attr->server_no
shuangy	1.1.2.2	198	+ (1l << branch_level);
shuangy	1.1.2.1	199	if(new_node_val >= dist_dir_attr->num_servers)
shuangy	1.1.2.2	200	{
shuangy	1.1.2.1	201	return -1;
shuangy	1.1.2.2	202	}
		203
		204	/* new node must be unset, otherwise branch_level is messed up */
		205	assert(!TST_BIT(bitmap, new_node_val));
shuangy	1.1.2.1	206
		207	return new_node_val;
		208	}
		209
		210	/*
		211	* update current bitmap tree and re-calculate branch_level
		212	*/
		213	int PINT_update_dist_dir_bitmap_from_bitmap(
shuangy	1.1.2.2	214	PVFS_dist_dir_attr *to_dir_attr,
		215	PVFS_dist_dir_bitmap to_dir_bitmap,
		216	const PVFS_dist_dir_attr *from_dir_attr,
		217	const PVFS_dist_dir_bitmap from_dir_bitmap)
shuangy	1.1.2.1	218	{
		219	int i;
		220
		221	assert((to_dir_attr != NULL) && (from_dir_attr != NULL));
shuangy	1.1.2.2	222	assert((to_dir_bitmap != NULL) && (from_dir_bitmap != NULL));
shuangy	1.1.2.1	223
		224	if( (to_dir_attr->num_servers != from_dir_attr->num_servers) \|\|
		225	(to_dir_attr->server_no == from_dir_attr->server_no))
shuangy	1.1.2.2	226	{
shuangy	1.1.2.1	227	return -1; /* not in the same tree or update itself */
shuangy	1.1.2.2	228	}
shuangy	1.1.2.1	229
		230	/* bitmap is with a type of (uint32_t *)
		231	*/
		232	for(i = to_dir_attr->bitmap_size - 1;
shuangy	1.1.2.2	233	i >= 0; i--)
shuangy	1.1.2.2	234	{
shuangy	1.1.2.1	235	to_dir_bitmap[i] \|= from_dir_bitmap[i];
		236	}
		237
		238	/* update branch level */
shuangy	1.1.2.2	239	if(to_dir_attr->server_no > -1) /* dirdata server */
shuangy	1.1.2.2	240	{
shuangy	1.1.2.1	241	to_dir_attr->branch_level = dist_dir_calc_branch_level(to_dir_attr, to_dir_bitmap);
shuangy	1.1.2.2	242	}
shuangy	1.1.2.1	243
		244	/* anything else to update? */
		245
		246	return 0;
		247	}
		248
		249
		250	/** a md5 encrypt function
		251	* MD5 encryption returns a 128bit value, the hash value takes the last 64bit
		252	* and save as an uint64_t
		253	*
		254	* ?? later, may add an option to be able to use other hash algorithm?
		255	*/
		256	PVFS_dist_dir_hash_type PINT_encrypt_dirdata(const char *const name)
		257	{
		258	PVFS_dist_dir_hash_type *hash_val;
		259	md5_state_t state;
		260	md5_byte_t digest[16];
		261
		262	md5_init(&state);
		263	md5_append(&state, (const md5_byte_t *)name, strlen(name));
		264	md5_finish(&state, digest);
		265
		266	hash_val = (PVFS_dist_dir_hash_type *)(digest + 8);
		267	return *hash_val;
		268	}
		269
		270	/*
		271	* Local variables:
		272	* c-indent-level: 4
		273	* c-basic-offset: 4
		274	* End:
		275	*
		276	* vim: ts=8 sts=4 sw=4 expandtab
		277	*/

FishEye

View

Diff

Annotations

Annotated File View