restore/node.c

/*
 * Copyright (c) 2000-2001 Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#include <xfs/xfs.h>
#include <xfs/jdm.h>

#include <unistd.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <errno.h>
#include <memory.h>
#include <limits.h>
#include <assert.h>

#include "config.h"

#include "types.h"
#include "mlog.h"
#include "win.h"
#include "node.h"
#include "mmap.h"

extern size_t pgsz;
extern size_t pgmask;

/* node handle limits
 */
#ifdef NODECHK

/* macros for manipulating node handles when handle consistency
 * checking is enabled. the upper bits of a handle will be loaded
 * with the node gen count, described below. this should not be
 * used for production code, it cuts into the number of dirents
 * that xfsrestore can handle.
 */
#define HDLGENCNT		4
#define	HDLGENSHIFT		( NBBY * sizeof ( nh_t ) - HDLGENCNT )
#define	HDLGENLOMASK		( ( 1 << HDLGENCNT ) - 1 )
#define	HDLGENMASK		( HDLGENLOMASK << HDLGENSHIFT )
#define HDLMASK			( ( 1 << HDLGENSHIFT ) - 1 )
#define HDLGETGEN( h )		( ( u_char_t )				\
				  ( ( ( int )h >> HDLGENSHIFT )		\
				    &					\
				    HDLGENLOMASK ))
#define HDLGETNHDL( h )		( ( nh_t )( ( int )h & HDLMASK ))
#define HDLMKHDL( g, n )	( ( nh_t )( ( ( ( int )g << HDLGENSHIFT )\
					      &				\
					      HDLGENMASK )		\
					  |				\
					  ( ( int )n & HDLMASK )))
#define NH_MAX			( HDLMASK )

/* the housekeeping byte of each node will hold two check fields:
 * a gen count, initialized to 0 and incremented each time a node
 * is allocated, to catch re-use of stale handles; and unique pattern, to
 * differentiate a valid node from random memory. two unique patterns will
 * be used; one when the node is on the free list, another when it is
 * allocated. this allows me to detect use of handles to nodes which have
 * be freed.
 */
#define HKPGENCNT		HDLGENCNT
#define HKPGENSHIFT		( NBBY - HKPGENCNT )
#define HKPGENLOMASK		( ( 1 << HKPGENCNT ) - 1 )
#define HKPGENMASK		( HKPGENLOMASK << HKPGENSHIFT )
#define HKPUNQCNT		( NBBY - HKPGENCNT )
#define HKPUNQMASK		( ( 1 << HKPUNQCNT ) - 1 )
#define HKPGETGEN( b )		( ( u_char_t )				\
				  ( ( ( int )b >> HKPGENSHIFT )		\
				    &					\
				    HKPGENLOMASK ))
#define HKPGETUNQ( b )		( ( u_char_t )( ( int )b & HKPUNQMASK ))
#define HKPMKHKP( g, u )	( ( u_char_t )				\
				  ( ( ( ( int )g << HKPGENSHIFT )	\
				      &					\
				      HKPGENMASK )			\
				    |					\
				    ( ( int )u & HKPUNQMASK )))

/* simple patterns for detecting a node
 */
#define NODEUNQFREE			0x9
#define NODEUNQALCD			0x6

#else /* NODECHK */

#define NH_MAX			( NH_NULL - 1 )

#endif /* NODECHK */

/* window constraints
 */
#define NODESPERSEG_MIN	1048576
#define WINMAP_MIN	4

/* reserve the firstpage for a header to save persistent context
 */
#define NODE_HDRSZ	pgsz

typedef int relnix_t;

struct node_hdr {
	size_t nh_nodesz;
		/* internal node size - user may see something smaller
		 */
	ix_t nh_nodehkix;
		/* index of byte in each node the user has reserved
		 * for use by me
		 */
	nh_t nh_nodesperseg;
		/* an integral number of internal nodes must fit into a
		 * segment
		 */
	size64_t nh_segsz;
		/* the backing store is partitoned into segment, which
		 * can be mapped into VM windows  by the win abstraction
		 */
	size_t nh_winmapmax;
		/* maximum number of windows which can be mapped
		 */
	size_t nh_nodealignsz;
		/* user's constraint on node alignment
		 */
	nh_t nh_freenh;
		/* handle of first node of singly-linked list of free nodes
		 */
	off64_t nh_firstsegoff;
		/* offset into backing store of the first segment
		 */
	nh_t nh_virgnh;
		/* handle of next virgin node
		 */
	int nh_segixshift;
		/* bitshift used to extract the segment index from an nh_t
		 */
	relnix_t nh_relnixmask;
		/* bitmask used to extract the node index from an nh_t
		 * (relative to the start of a segment)
		 */
};

typedef struct node_hdr node_hdr_t;

static node_hdr_t *node_hdrp;
static int node_fd;

static inline segix_t
nh2segix( nh_t nh )
{
	return nh >> node_hdrp->nh_segixshift;
}

static inline relnix_t
nh2relnix( nh_t nh )
{
	return nh & node_hdrp->nh_relnixmask;
}

static inline void
node_map_internal( nh_t nh, void **pp )
{
	win_map( nh2segix( nh ), pp );
	if ( *pp != NULL ) {
		relnix_t relnix = nh2relnix( nh );
		*pp = ( void * )( ( char * )( *pp ) +
				( ( off64_t )relnix *
				  node_hdrp->nh_nodesz ) );
	}
}

/* ARGSUSED */
static inline void
node_unmap_internal( nh_t nh, void **pp, bool_t freepr )
{
#ifdef NODECHK
	register u_char_t hkp;
	register u_char_t hdlgen;
	register u_char_t nodegen;
	register u_char_t nodeunq;
#endif /* NODECHK */

	assert( pp );
	assert( *pp );
	assert( nh != NH_NULL );

	/* convert the handle into an index
	 */
#ifdef NODECHK
	hdlgen = HDLGETGEN( nh );
	nh = HDLGETNHDL( nh );
#endif /* NODECHK */

	assert( nh <= NH_MAX );

#ifdef NODECHK
	hkp = *( *( u_char_t ** )pp + node_hdrp->nh_nodehkix );
	nodegen = HKPGETGEN( hkp );
	assert( nodegen == hdlgen );
	nodeunq = HKPGETUNQ( hkp );
	if ( ! freepr ) {
		assert( nodeunq != NODEUNQFREE );
		assert( nodeunq == NODEUNQALCD );
	} else {
		assert( nodeunq != NODEUNQALCD );
		assert( nodeunq == NODEUNQFREE );
	}
#endif /* NODECHK */

	/* unmap the window containing the node
	 */
	win_unmap( nh2segix( nh ), pp ); /* zeros *pp */
}

/* ARGSUSED */
bool_t
node_init( int fd,
	   off64_t off,
	   size_t usrnodesz,
	   ix_t nodehkix,
	   size_t nodealignsz,
	   size64_t vmsz,
	   size64_t dirs_nondirs_cnt )
{
	size_t nodesz;
	size64_t segsz;
	nh_t nodesperseg;
	size_t max_segments;
	size_t winmapmax;
	size_t segcount;
	int segixshift;

	/* sanity checks
	 */
	assert( sizeof( node_hdr_t ) <= NODE_HDRSZ );
	assert( sizeof( nh_t ) < sizeof( off64_t ));
	assert( sizeof( nh_t ) <= sizeof( segix_t ));
	assert( sizeof( nh_t ) <= sizeof( relnix_t ));
	assert( nodehkix < usrnodesz );
	assert( usrnodesz >= sizeof( char * ) + 1 );
		/* so node is at least big enough to hold
		 * the free list linkage and the housekeeping byte
		 */
	assert( nodehkix > sizeof( char * ));
		/* since beginning of each node is used to
		 * link it in the free list.
		 */

	/* adjust the user's node size to meet user's alignment constraint
	*/
	nodesz = ( usrnodesz + nodealignsz - 1 ) & ~( nodealignsz - 1 );

	/* Calculate the node table params based on the number of inodes in the
	 * dump, since that's all we know. Ideally we'd base this on the number
	 * of dirents in the dump instead as there's a node per dirent.
	 *
	 * Due to virtual memory constraints and the fact that we don't know
	 * the final node table size, we can't guarantee that the entire node
	 * table can be mapped at once. Instead segments will be mapped using a
	 * window abstraction. Some operations require WINMAP_MIN nodes to be
	 * referenced at a time, therefore we must ensure that this many
	 * segments fit in virtual memory.
	 *
	 * nodesperseg must be a power of two. Earlier versions did not enforce
	 * this, and profiling showed that nearly 50% of cpu time during the
	 * node table construction was consumed doing division and modulo to
	 * convert an nh_t to a segment index and node offset.  By making
	 * nodesperseg a power of two we can use shift and bitwise-and instead.
	 *
	 * Each segment must hold an integral number of nodes and be an integral
	 * number of pages. #1 ensures this except when nodesperseg is small, so
	 * the smallest allowed segsz is pgsz * nodesz (i.e., nodesperseg ==
	 * pgsz). However this is of no consequence as we enforce a larger
	 * minimum nodesperseg (NODESPERSEG_MIN) anyway in order to place a
	 * reasonable cap on the max number of segments.
	 */

	assert( NODESPERSEG_MIN >= pgsz );

	if ( vmsz < WINMAP_MIN * NODESPERSEG_MIN * nodesz ) {
		mlog( MLOG_NORMAL | MLOG_ERROR, _(
		  "not enough virtual memory for node abstraction: "
		  "remaining-vsmz=%llu need=%llu\n"),
		  vmsz, WINMAP_MIN * NODESPERSEG_MIN * nodesz );
		return BOOL_FALSE;
	}

	/* This is checked as nodes are allocated as well (remember that
	 * dirs_nondirs_cnt may be less than the number of nodes/dirents).
	 * Checking this here prevents potential overflow in the logic below.
	 */
	if ( dirs_nondirs_cnt > NH_MAX ) {
		mlog( MLOG_NORMAL | MLOG_ERROR, _(
		  "dump contains %llu inodes, restore can only handle %u\n"),
		  dirs_nondirs_cnt, NH_MAX );
		return BOOL_FALSE;
	}

	for ( winmapmax = 0, segcount = 1; winmapmax < WINMAP_MIN; segcount <<= 1 ) {

		nodesperseg = max( dirs_nondirs_cnt / segcount, NODESPERSEG_MIN );

		/* nodesperseg must be a power of 2 */
		for ( segixshift = 0;
		      ( 1ULL << segixshift ) < nodesperseg;
		      segixshift++ );

		/* rounding up to a power of 2 may have caused overflow */
		if ( ( 1ULL << segixshift ) > NH_MAX )
			segixshift--;

		nodesperseg = 1UL << segixshift;

		max_segments = 1UL << ( NBBY * sizeof(nh_t) - segixshift );

		segsz = nodesperseg * nodesz;

		/* max number of segments that will fit in virtual memory,
		 * capped at the max possible number of segments
		 */
		winmapmax = min( vmsz / segsz, max_segments );
	}

	/* map the abstraction header
	 */
	assert( ( NODE_HDRSZ & pgmask ) == 0 );
	assert( ! ( NODE_HDRSZ % pgsz ));
	assert( off <= OFF64MAX );
	assert( ! ( off % ( off64_t )pgsz ));
	node_hdrp = ( node_hdr_t * )mmap_autogrow(
					    NODE_HDRSZ,
					    fd,
					    off );
	if ( node_hdrp == (node_hdr_t *)-1 ) {
	    mlog( MLOG_NORMAL | MLOG_ERROR, _(
		  "unable to map node hdr of size %d: %s\n"),
		  NODE_HDRSZ,
		  strerror( errno ));
	    return BOOL_FALSE;
	}

	/* initialize and save persistent context.
	 */
	node_hdrp->nh_nodesz = nodesz;
	node_hdrp->nh_nodehkix = nodehkix;
	node_hdrp->nh_segsz = segsz;
	node_hdrp->nh_winmapmax = winmapmax;
	node_hdrp->nh_nodesperseg = nodesperseg;
	node_hdrp->nh_nodealignsz = nodealignsz;
	node_hdrp->nh_freenh = NH_NULL;
	node_hdrp->nh_firstsegoff = off + ( off64_t )NODE_HDRSZ;
	node_hdrp->nh_virgnh = 0;
	node_hdrp->nh_segixshift = segixshift;
	node_hdrp->nh_relnixmask = nodesperseg - 1;

	/* save transient context
	 */
	node_fd = fd;

	/* initialize the window abstraction
	 */
	win_init( fd,
		  node_hdrp->nh_firstsegoff,
		  segsz,
		  winmapmax );
	
	/* announce the results
	 */
	mlog( MLOG_DEBUG | MLOG_TREE,
	      "node_init:"
	      " vmsz = %llu (0x%llx)"
	      " segsz = %llu (0x%llx)"
	      " nodesperseg = %u (0x%x)"
	      " winmapmax = %lu (0x%lx)"
	      "\n",
	      vmsz, vmsz,
	      segsz, segsz,
	      nodesperseg, nodesperseg,
	      winmapmax, winmapmax );

	return BOOL_TRUE;
}

bool_t
node_sync( int fd, off64_t off )
{
	/* sanity checks
	 */
	assert( sizeof( node_hdr_t ) <= NODE_HDRSZ );

	/* map the abstraction header
	 */
	assert( ( NODE_HDRSZ & pgmask ) == 0 );
	assert( off <= ( off64_t )OFF64MAX );
	assert( ! ( off % ( off64_t )pgsz ));
	node_hdrp = ( node_hdr_t * )mmap_autogrow(
					    NODE_HDRSZ,
					    fd,
					    off );
	if ( node_hdrp == (node_hdr_t *)-1 ) {
		mlog( MLOG_NORMAL | MLOG_ERROR, _(
		      "unable to map node hdr of size %d: %s\n"),
		      NODE_HDRSZ,
		      strerror( errno ));
		return BOOL_FALSE;
	}

	/* save transient context
	 */
	node_fd = fd;

	/* initialize the window abstraction
	 */
	win_init( fd,
		  node_hdrp->nh_firstsegoff,
		  node_hdrp->nh_segsz,
		  node_hdrp->nh_winmapmax );

	return BOOL_TRUE;
}

nh_t
node_alloc( void )
{
	u_char_t *p;
	nh_t nh;
#ifdef NODECHK
	u_char_t *hkpp;
	u_char_t gen = 0;
	u_char_t unq;
#endif /* NODECHK */

	/* if there's a node available on the free list, use it.
	 * otherwise get the next one from the current virgin segment,
	 * or allocate a new virgin segment if the current one is depleted.
	 */
	if ( node_hdrp->nh_freenh != NH_NULL ) {
		nh_t *linkagep;

		nh = node_hdrp->nh_freenh;

		node_map_internal( nh, ( void ** )&p );
		if (p == NULL)
			return NH_NULL;
#ifdef NODECHK
		hkpp = p + node_hdrp->nh_nodehkix;
		gen = ( u_char_t )( HKPGETGEN( *p ) + ( u_char_t )1 );
		unq = HKPGETUNQ( *hkpp );
		assert( unq != NODEUNQALCD );
		assert( unq == NODEUNQFREE );
#endif /* NODECHK */

		/* adjust the free list */
		linkagep = ( nh_t * )p;
		node_hdrp->nh_freenh = *linkagep;

		node_unmap_internal( nh, ( void ** )&p, BOOL_TRUE );

	} else {
		if ( nh2relnix( node_hdrp->nh_virgnh ) == 0 ) {
			/* need to start a new virgin segment */
			int rval;
			off64_t new_seg_off =
				node_hdrp->nh_firstsegoff +
				( off64_t )nh2segix( node_hdrp->nh_virgnh ) *
				( off64_t )node_hdrp->nh_segsz;

			assert( new_seg_off
				<=
				OFF64MAX - ( off64_t )node_hdrp->nh_segsz );
			mlog( MLOG_DEBUG,
			      "pre-growing new node array segment at %lld "
			      "size %lld\n",
			      new_seg_off,
			      ( off64_t )node_hdrp->nh_segsz );
			rval = ftruncate64( node_fd,
					    new_seg_off
					    +
					    ( off64_t )node_hdrp->nh_segsz );
			if ( rval ) {
				mlog( MLOG_NORMAL | MLOG_WARNING | MLOG_TREE, _(
				      "unable to autogrow node segment %u: "
				      "%s (%d)\n"),
				      nh2segix( node_hdrp->nh_virgnh ),
				      strerror( errno ),
				      errno );
			}
		}

		nh = node_hdrp->nh_virgnh++;
	}

	/* build a handle for node
	 */
	if ( nh > NH_MAX ) {
		mlog( MLOG_NORMAL | MLOG_ERROR, _(
		  "dump contains too many dirents, "
		  "restore can only handle %llu\n"),
		  NH_MAX );
		return NH_NULL;
	}
#ifdef NODECHK
	node_map_internal( nh , ( void ** )&p );
	if (p == NULL)
		abort();
	hkpp = p + ( int )node_hdrp->nh_nodehkix;
	nh = HDLMKHDL( gen, nh );
	*hkpp = HKPMKHKP( gen, NODEUNQALCD );
	node_unmap_internal( nh, ( void ** )&p, BOOL_FALSE );
#endif /* NODECHK */

	return nh;
}

void *
node_map( nh_t nh )
{
	u_char_t *p;
#ifdef NODECHK
	register u_char_t hkp;
	register u_char_t hdlgen;
	register u_char_t nodegen;
	register u_char_t nodeunq;
#endif /* NODECHK */

	assert( nh != NH_NULL );

	/* convert the handle into an index
	 */
#ifdef NODECHK
	hdlgen = HDLGETGEN( nh );
	nh = HDLGETNHDL( nh );
#endif /* NODECHK */

	assert( nh <= NH_MAX );

	/* map in
	 */
	p = 0; /* keep lint happy */
	node_map_internal( nh, ( void ** )&p );
	if (p == NULL)
	    return NULL;

#ifdef NODECHK
	hkp = *( p + node_hdrp->nh_nodehkix );
	nodegen = HKPGETGEN( hkp );
	nodeunq = HKPGETUNQ( hkp );
	assert( nodegen == hdlgen );
	assert( nodeunq != NODEUNQFREE );
	assert( nodeunq == NODEUNQALCD );
#endif /* NODECHK */

	return ( void * )p;
}

void
node_unmap( nh_t nh, void **pp )
{
	node_unmap_internal( nh, pp, BOOL_FALSE );
}

void
node_free( nh_t *nhp )
{
	nh_t nh;
	u_char_t *p;
	register nh_t *linkagep;
#ifdef NODECHK
	register u_char_t *hkpp;
	register u_char_t hdlgen;
	register u_char_t nodegen;
	register u_char_t nodeunq;
#endif /* NODECHK */

	assert( nhp );
	nh = *nhp;
	assert( nh != NH_NULL );

	/* convert the handle into an index
	 */
#ifdef NODECHK
	hdlgen = HDLGETGEN( nh );
	nh = HDLGETNHDL( nh );
#endif /* NODECHK */

	assert( nh <= NH_MAX );

	/* map in
	 */
	p = ( u_char_t * )node_map( nh );
	if (p == NULL){
	    *nhp = NH_NULL;
	    return;
	}

#ifdef NODECHK
	/* fix up unique field
	 */
	hkpp = p + node_hdrp->nh_nodehkix;
	nodegen = HKPGETGEN( *hkpp );
	nodeunq = HKPGETUNQ( *hkpp );
	assert( nodegen == hdlgen );
	assert( nodeunq != NODEUNQFREE );
	assert( nodeunq == NODEUNQALCD );
	*hkpp = HKPMKHKP( nodegen, NODEUNQFREE );
#endif /* NODECHK */

	/* put node on free list
	 */
	linkagep = ( nh_t * )p;
	*linkagep = node_hdrp->nh_freenh;
	node_hdrp->nh_freenh = nh;

	/* map out
	 */
	node_unmap_internal( nh, ( void ** )&p, BOOL_TRUE );

	/* invalidate caller's handle
	 */
	*nhp = NH_NULL;
}