alenlist.c

Linux内核源代码 为压缩文件 是<<Linux内核>>一书中的源代码

		if (!(flags & AL_NOCOMPACT) &&
		    (alenlist->al_compaction_address == address)) {
			last_index = (alenlist->al_logical_size-1) % ALEN_CHUNK_SZ;
			alenp = &(alenlist->al_last_chunk->alc_pair[last_index]);
			alenp->al_length += length;
			alenlist->al_compaction_address += length;
			return(ALENLIST_SUCCESS);
		}

		/*
		 * If we're out of room in this chunk, move to a new chunk.
	 	 */
		if (index == 0) {
			if (alenlist->al_flags & AL_FIXED_SIZE) {
				alenlist->al_last_chunk = alenlist->al_last_chunk->alc_next;

				/* If we're out of space in a FIXED_SIZE List, quit. */
				if (alenlist->al_last_chunk == NULL) {
					ASSERT(alenlist->al_logical_size == alenlist->al_actual_size);
					return(ALENLIST_FAILURE);
				}
			} else {
				alenlist_chunk_t new_chunk;

				new_chunk = kmem_zone_alloc(alenlist_chunk_zone, 
							flags & AL_NOSLEEP ? VM_NOSLEEP : 0);

				if (new_chunk == NULL)
					return(ALENLIST_FAILURE);

				alenlist->al_last_chunk->alc_next = new_chunk;
				new_chunk->alc_next = NULL;
				alenlist->al_last_chunk = new_chunk;
				alenlist->al_actual_size += ALEN_CHUNK_SZ;
				INCR_COUNT(&alenlist_chunk_count);
			}
		}
	}

	alenp = &(alenlist->al_last_chunk->alc_pair[index]);
	alenp->al_addr = address;
	alenp->al_length = length;
	
	alenlist->al_logical_size++;
	alenlist->al_compaction_address = address + length;

	return(ALENLIST_SUCCESS);
}


/*
 * Replace an item in an Address/Length List.  Cursor is updated so
 * that alenlist_get will get the next item in the list.  This interface 
 * is not very useful for drivers; but it is useful to bus providers 
 * that need to translate between address spaced in situ.  The old Address
 * and Length are returned.
 */
/* ARGSUSED */
int
alenlist_replace(	alenlist_t alenlist, 		/* in: replace in this list */
			alenlist_cursor_t cursorp, 	/* inout: which item to replace */
			alenaddr_t *addrp, 		/* inout: address */
			size_t *lengthp,		/* inout: length */
			unsigned flags)
{
	alen_t *alenp;
	alenlist_chunk_t chunk;
	unsigned int index;
	size_t length;
	alenaddr_t addr;

	if ((addrp == NULL) || (lengthp == NULL))
		return(ALENLIST_FAILURE);

	if (alenlist->al_logical_size == 0)
		return(ALENLIST_FAILURE);

	addr = *addrp;
	length = *lengthp;

	/* 
	 * If no cursor explicitly specified, use the Address/Length List's 
	 * internal cursor.
	 */
	if (cursorp == NULL)
		cursorp = &alenlist->al_cursor;

	chunk = cursorp->al_chunk;
	index = cursorp->al_index;

	ASSERT(cursorp->al_alenlist == alenlist);
	if (cursorp->al_alenlist != alenlist)
		return(ALENLIST_FAILURE);

	alenp = &chunk->alc_pair[index];

	/* Return old values */
	*addrp = alenp->al_length;
	*lengthp = alenp->al_addr;

	/* Set up new values */
	alenp->al_length = length;
	alenp->al_addr = addr;

	/* Update cursor to point to next item */
	cursorp->al_bcount = length;

	return(ALENLIST_SUCCESS);
}


/*
 * Initialize a cursor in order to walk an alenlist.
 * An alenlist_cursor always points to the last thing that was obtained
 * from the list.  If al_chunk is NULL, then nothing has yet been obtained.
 *
 * Note: There is an "internal cursor" associated with every Address/Length List.
 * For users that scan sequentially through a List, it is more efficient to
 * simply use the internal cursor.  The caller must insure that no other users
 * will simultaneously scan the List.  The caller can reposition the internal
 * cursor by calling alenlist_cursor_init with a NULL cursorp.
 */
int
alenlist_cursor_init(alenlist_t alenlist, size_t offset, alenlist_cursor_t cursorp)
{
	size_t byte_count;

	if (cursorp == NULL)
		cursorp = &alenlist->al_cursor;

	/* Get internal cursor's byte count for use as a hint.
	 *
	 * If the internal cursor points passed the point that we're interested in,
	 * we need to seek forward from the beginning.  Otherwise, we can seek forward
	 * from the internal cursor.
	 */
	if ((offset > 0) &&
	   ((byte_count = alenlist_cursor_offset(alenlist, (alenlist_cursor_t)NULL)) <= offset)) {
		offset -= byte_count;
		alenlist_cursor_clone(alenlist, NULL, cursorp);
	} else
		do_cursor_init(alenlist, cursorp);

	/* We could easily speed this up, but it shouldn't be used very often. */
	while (offset != 0) {
		alenaddr_t addr;
		size_t length;

		if (alenlist_get(alenlist, cursorp, offset, &addr, &length, 0) != ALENLIST_SUCCESS)
			return(ALENLIST_FAILURE);
		offset -= length;
	}
	return(ALENLIST_SUCCESS);
}


/*
 * Copy a cursor.  The source cursor is either an internal alenlist cursor
 * or an explicit cursor.
 */
int
alenlist_cursor_clone(	alenlist_t alenlist, 
			alenlist_cursor_t cursorp_in, 
			alenlist_cursor_t cursorp_out)
{
	ASSERT(cursorp_out);

	if (alenlist && cursorp_in)
		if (alenlist != cursorp_in->al_alenlist)
			return(ALENLIST_FAILURE);

	if (alenlist)
		*cursorp_out = alenlist->al_cursor; /* small structure copy */
	else if (cursorp_in)
		*cursorp_out = *cursorp_in; /* small structure copy */
	else
		return(ALENLIST_FAILURE); /* no source */

	return(ALENLIST_SUCCESS);
}

/*
 * Return the number of bytes passed so far according to the specified cursor.
 * If cursorp is NULL, use the alenlist's internal cursor.
 */
size_t
alenlist_cursor_offset(alenlist_t alenlist, alenlist_cursor_t cursorp)
{
	ASSERT(!alenlist || !cursorp || (alenlist == cursorp->al_alenlist));

	if (cursorp == NULL) {
		ASSERT(alenlist);
		cursorp = &alenlist->al_cursor;
	}

	return(cursorp->al_offset);
}

/*
 * Allocate and initialize an Address/Length List cursor.
 */
alenlist_cursor_t
alenlist_cursor_create(alenlist_t alenlist, unsigned flags)
{
	alenlist_cursor_t cursorp;

	ASSERT(alenlist != NULL);
	cursorp = kmem_zone_alloc(alenlist_cursor_zone, flags & AL_NOSLEEP ? VM_NOSLEEP : 0);
	if (cursorp) {
		INCR_COUNT(&alenlist_cursor_count);
		alenlist_cursor_init(alenlist, 0, cursorp);
	}
	return(cursorp);
}

/*
 * Free an Address/Length List cursor.
 */
void
alenlist_cursor_destroy(alenlist_cursor_t cursorp)
{
	DECR_COUNT(&alenlist_cursor_count);
	kmem_zone_free(alenlist_cursor_zone, cursorp);
}


/*
 * Fetch an address/length pair from an Address/Length List.  Update
 * the "cursor" so that next time this routine is called, we'll get
 * the next address range.  Never return a length that exceeds maxlength
 * (if non-zero).  If maxlength is a power of 2, never return a length 
 * that crosses a maxlength boundary.  [This may seem strange at first,
 * but it's what many drivers want.]
 *
 * Returns: SUCCESS/FAILURE
 */
int
alenlist_get(	alenlist_t alenlist, 		/* in: get from this list */
		alenlist_cursor_t cursorp, 	/* inout: which item to get */
		size_t	maxlength,		/* in: at most this length */
		alenaddr_t *addrp, 		/* out: address */
		size_t *lengthp,		/* out: length */
		unsigned flags)
{
	alen_t *alenp;
	alenlist_chunk_t chunk;
	unsigned int index;
	size_t bcount;
	size_t length;

	/* 
	 * If no cursor explicitly specified, use the Address/Length List's 
	 * internal cursor.
	 */
	if (cursorp == NULL) {
		if (alenlist->al_logical_size == 0)
			return(ALENLIST_FAILURE);
		cursorp = &alenlist->al_cursor;
	}

	chunk = cursorp->al_chunk;
	index = cursorp->al_index;
	bcount = cursorp->al_bcount;

	ASSERT(cursorp->al_alenlist == alenlist);
	if (cursorp->al_alenlist != alenlist)
		return(ALENLIST_FAILURE);

	alenp = &chunk->alc_pair[index];
	length = alenp->al_length - bcount;

	/* Bump up to next pair, if we're done with this pair. */
	if (length == 0) {
		cursorp->al_bcount = bcount = 0;
		cursorp->al_index = index = (index + 1) % ALEN_CHUNK_SZ;

		/* Bump up to next chunk, if we're done with this chunk. */
		if (index == 0) {
			if (cursorp->al_chunk == alenlist->al_last_chunk)
				return(ALENLIST_FAILURE);
			chunk = chunk->alc_next;
			ASSERT(chunk != NULL);
		} else {
			/* If in last chunk, don't go beyond end. */
			if (cursorp->al_chunk == alenlist->al_last_chunk) {
				int last_size = alenlist->al_logical_size % ALEN_CHUNK_SZ;
				if (last_size && (index >= last_size))
					return(ALENLIST_FAILURE);
			}
		}

		alenp = &chunk->alc_pair[index];
		length = alenp->al_length;
	}

	/* Constrain what we return according to maxlength */
	if (maxlength) {
		size_t maxlen1 = maxlength - 1;

		if ((maxlength & maxlen1) == 0) /* power of 2 */
			maxlength -= 
			   ((alenp->al_addr + cursorp->al_bcount) & maxlen1);

		length = MIN(maxlength, length);
	}

	/* Update the cursor, if desired. */
	if (!(flags & AL_LEAVE_CURSOR)) {
		cursorp->al_bcount += length;
		cursorp->al_chunk = chunk;
	}

	*lengthp = length;
	*addrp = alenp->al_addr + bcount;

	return(ALENLIST_SUCCESS);
}


/*
 * Return the number of pairs in the specified Address/Length List.
 * (For FIXED_SIZE Lists, this returns the logical size of the List, 
 * not the actual capacity of the List.)
 */
int
alenlist_size(alenlist_t alenlist)
{
	return(alenlist->al_logical_size);
}


/*
 * Concatenate two Address/Length Lists.
 */
void
alenlist_concat(alenlist_t from,
		alenlist_t to)
{
	struct alenlist_cursor_s cursor;
	alenaddr_t addr;
	size_t length;

	alenlist_cursor_init(from, 0, &cursor);

	while(alenlist_get(from, &cursor, (size_t)0, &addr, &length, 0) == ALENLIST_SUCCESS)
		alenlist_append(to, addr, length, 0);
}

/*
 * Create a copy of a list.
 * (Not all attributes of the old list are cloned.  For instance, if
 * a FIXED_SIZE list is cloned, the resulting list is NOT FIXED_SIZE.)
 */
alenlist_t
alenlist_clone(alenlist_t old_list, unsigned flags)
{
	alenlist_t new_list;

	new_list = alenlist_create(flags);
	if (new_list != NULL)
		alenlist_concat(old_list, new_list);

	return(new_list);
}


/* 
 * Convert a kernel virtual address to a Physical Address/Length List.
 */
alenlist_t
kvaddr_to_alenlist(alenlist_t alenlist, caddr_t kvaddr, size_t length, unsigned flags)
{
	alenaddr_t paddr;
	long offset;
	size_t piece_length;
	int created_alenlist;

	if (length <=0)
		return(NULL);

	/* If caller supplied a List, use it.  Otherwise, allocate one. */
	if (alenlist == NULL) {
		alenlist = alenlist_create(0);
		created_alenlist = 1;
	} else {
		alenlist_clear(alenlist);
		created_alenlist = 0;
	}

	paddr = kvtophys(kvaddr);
	offset = poff(kvaddr);

	/* Handle first page */
	piece_length = MIN(NBPP - offset, length);
	if (alenlist_append(alenlist, paddr, piece_length, flags) == ALENLIST_FAILURE)
		goto failure;
	length -= piece_length;
	kvaddr += piece_length;

	/* Handle middle pages */
	while (length >= NBPP) {
		paddr = kvtophys(kvaddr);
		if (alenlist_append(alenlist, paddr, NBPP, flags) == ALENLIST_FAILURE)
			goto failure;
		length -= NBPP;
		kvaddr += NBPP;
	}

	/* Handle last page */
	if (length) {
		ASSERT(length < NBPP);
		paddr = kvtophys(kvaddr);
		if (alenlist_append(alenlist, paddr, length, flags) == ALENLIST_FAILURE)
			goto failure;
	}

	alenlist_cursor_init(alenlist, 0, NULL);
	return(alenlist);

failure:
	if (created_alenlist)
		alenlist_destroy(alenlist);
	return(NULL);
}


#if DEBUG
static void
alenlist_show(alenlist_t alenlist)
{
	struct alenlist_cursor_s cursor;
	alenaddr_t addr;
	size_t length;
	int i = 0;

	alenlist_cursor_init(alenlist, 0, &cursor);

	qprintf("Address/Length List@0x%x:\n", alenlist);
	qprintf("logical size=0x%x actual size=0x%x last_chunk at 0x%x\n", 
		alenlist->al_logical_size, alenlist->al_actual_size, 
		alenlist->al_last_chunk);
	qprintf("cursor: chunk=0x%x index=%d offset=0x%x\n",
		alenlist->al_cursor.al_chunk, 
		alenlist->al_cursor.al_index,
		alenlist->al_cursor.al_bcount);
	while(alenlist_get(alenlist, &cursor, (size_t)0, &addr, &length, 0) == ALENLIST_SUCCESS)
		qprintf("%d:\t0x%lx 0x%lx\n", ++i, addr, length);
}
#endif /* DEBUG */