buffer.c

linux下自动mount各种即插即用设备的一个小程序源码 文件包含内容： /vold.h /vold.c /split.h /split.c /disktype-6/disktype.c

/*
 * buffer.c
 * Manages data reading and caching.
 *
 * Copyright (c) 2003 Christoph Pfisterer
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE. 
 */

#include "detect.h"

#define PROFILE 0

/*
 * constants
 */

/* this defines 4K chunks, should only be changed upwards */
#define CHUNKBITS (12)
#define CHUNKSIZE (1<<CHUNKBITS)
#define CHUNKMASK (CHUNKSIZE-1)

/* the minimum block size for block-oriented sources, maximum is the
   chunk size */
#define MINBLOCKSIZE (256)

/* a simple hash function */
#define HASHSIZE (13)
#define HASHFUNC(start) (((start)>>CHUNKBITS) % HASHSIZE)

/* convenience */
#define MINIMUM(a,b) (((a) < (b)) ? (a) : (b))
#define MAXIMUM(a,b) (((a) > (b)) ? (a) : (b))

/*
 * types
 */

typedef struct chunk {
	/* file positions
	   start never changes and is CHUNKSIZE-aligned, it identifies the chunk
	   len is between 0 and CHUNKSIZE
	   end is kept synchronized to (start + len)
	*/
	U64 start, end, len;
	void *buf;
	/* links within a hash bucket, organized as a ring list */
	struct chunk *next, *prev;
}
CHUNK;

typedef struct cache {
	/* chunks stored as a hash table of ring lists */
	CHUNK *hashtab[HASHSIZE];
	/* temporary buffer for requests involving several chunks */
	void *tempbuf;
}
CACHE;

/*
 * helper functions
 */

static CHUNK * ensure_chunk(SOURCE *s, CACHE *cache, U64 start);
static CHUNK * get_chunk_alloc(CACHE *cache, U64 start);

/*
 * retrieve a piece of the source, entry point for detection
 */

U64 get_buffer(SECTION *section, U64 pos, U64 len, void **buf) {
	SOURCE *s;

	/* get source info */
	s = section->source;
	pos += section->pos;

	return get_buffer_real(s, pos, len, NULL, buf);
}

/*
 * actual retrieval, entry point for layering
 */

U64 get_buffer_real(SOURCE *s, U64 pos, U64 len, void *inbuf, void **outbuf) {
	CACHE *cache;
	CHUNK *c;
	U64 end, first_chunk, last_chunk, curr_chunk, got, tocopy;
	void *mybuf;

	/* sanity check */
	if (len == 0 || (inbuf == NULL && outbuf == NULL))
		return 0;

	/* get source info */
	if (s->size_known && pos >= s->size) {
		/* error("Request for data beyond end of file (pos %llu)", pos); */
		return 0;
	}
	end = pos + len;
	if (s->size_known && end > s->size) {
		/* truncate to known end of file */
		end = s->size;
		len = end - pos;
	}

	/* get cache head */
	cache = (CACHE *)s->cache_head;
	if (cache == NULL) {
		/* allocate and initialize new cache head */
		cache = (CACHE *)malloc(sizeof(CACHE));
		if (cache == NULL)
			bailout("Out of memory");
		memset(cache, 0, sizeof(CACHE));
		s->cache_head = (void *)cache;
	}
	/* free old temp buffer if present */
	if (cache->tempbuf != NULL) {
		free(cache->tempbuf);
		cache->tempbuf = NULL;
	}

	/* calculate involved chunks */
	first_chunk = pos & ~CHUNKMASK;
	last_chunk = (end - 1) & ~CHUNKMASK;

	if (last_chunk == first_chunk) {
		/* just get the matching chunk */
		c = ensure_chunk(s, cache, first_chunk);
		/* NOTE: first_chunk == c->start */

		if (pos >= c->end)  /* chunk is incomplete and doesn't have our data */
			return 0;

		/* calculate return data */
		len = MINIMUM(len, c->end - pos);  /* guaranteed to be > 0 */
		mybuf = c->buf + (pos - c->start);
		if (inbuf)
			memcpy(inbuf, mybuf, len);
		if (outbuf)
			*outbuf = mybuf;

		return len;

	} else {

		/* prepare a buffer for concatenation */
		if (inbuf) {
			mybuf = inbuf;
		} else {

#if PROFILE
			printf("Temporary buffer for request %llu:%llu\n", pos, len);
#endif

			/* allocate one temporarily, will be free()'d at the next call */
			cache->tempbuf = malloc(len);
			if (cache->tempbuf == NULL) {
				error("Out of memory, still going");
				return 0;
			}
			mybuf = cache->tempbuf;
		}

		/* draw data from all covered chunks */
		got = 0;
		for (curr_chunk = first_chunk; curr_chunk <= last_chunk;
		        curr_chunk += CHUNKSIZE) {
			/* get that chunk */
			c = ensure_chunk(s, cache, curr_chunk);
			/* NOTE: curr_chunk == c->start */

			if (pos > curr_chunk) {
				/* copy from middle of chunk */
				/* NOTE:
				   - we're in the first chunk, i.e. pos < curr_chunk + CHUNKSIZE
				   - pos >= curr_chunk
				   - got == 0
				   - we must read to the end (else it would be the one-chunk case),
				     i.e. pos + len > curr_chunk + CHUNKSIZE
				   BUT: the chunk may be only partially filled
				*/
				if (c->end > pos) {
					tocopy = c->end - pos;
					memcpy(mybuf, c->buf + (pos & CHUNKMASK), tocopy);
				} else
					tocopy = 0;
			} else {
				/* copy from start of chunk */
				tocopy = MINIMUM(c->len, len - got);  /* c->len can be zero */
				if (tocopy)
					memcpy(mybuf + got, c->buf, tocopy);
			}
			got += tocopy;

			/* stop after an incomplete chunk (possibly-okay for the last one,
			not-so-nice for earlier ones, but treated all the same) */
			if (c->len < CHUNKSIZE)
				break;
		}

		/* calculate return data */
		len = MINIMUM(len, got);  /* may be zero */
		if (outbuf)
			*outbuf = mybuf;
		return len;

	}
}

static CHUNK * ensure_chunk(SOURCE *s, CACHE *cache, U64 start) {
	CHUNK *c;
	U64 pos, rel_start, rel_end;
	U64 toread, result, curr_chunk;

	c = get_chunk_alloc(cache, start);
	if (c->len >= CHUNKSIZE || (s->size_known && c->end >= s->size)) {
		/* chunk is complete  or  complete until EOF */
		return c;
	}

	if (s->sequential) {
		/* sequential source: ensure all data before this chunk was read */

		if (s->seq_pos < start) {
			/* try to read data between seq_pos and start */
			curr_chunk = s->seq_pos & ~CHUNKMASK;
			while (curr_chunk < start) {  /* runs at least once, due to the if()
								       and the formula of curr_chunk */
				ensure_chunk(s, cache, curr_chunk);
				curr_chunk += CHUNKSIZE;
				if (s->seq_pos < curr_chunk)
					break;  /* it didn't work out... */
			}

			/* re-check precondition since s->size may have changed */
			if (s->size_known && c->end >= s->size)
				return c;  /* there is no more data to read */
		}

		if (s->seq_pos != c->end)   /* c->end is where we'll continue reading */
			return c;  /* we're not in a sane state, give up */
	}

	/* try to read the missing piece */
	if (s->read_block != NULL) {
		/* use block-oriented read_block() method */

		if (s->blocksize < MINBLOCKSIZE ||
		        s->blocksize > CHUNKSIZE ||
		        ((s->blocksize & (s->blocksize - 1)) != 0)) {
			bailout("Internal error: Invalid block size %d", s->blocksize);
		}

		for (rel_start = 0; rel_start < CHUNKSIZE; rel_start = rel_end) {
			rel_end = rel_start + s->blocksize;
			if (c->len >= rel_end)
				continue;  /* already read */
			pos = c->start + rel_start;
			if (s->size_known && pos >= s->size)
				break;     /* whole block is past end of file */

			/* read it */
			if (s->read_block(s, pos, c->buf + rel_start)) {
				/* success */
				c->len = rel_end;
				c->end = c->start + c->len;
			} else {
				/* failure */
				c->len = rel_start;  /* this is safe as it can only mean a shrink */
				c->end = c->start + c->len;
				/* note the new end of file if necessary */
				if (!s->size_known || s->size > c->end) {
					s->size_known = 1;
					s->size = c->end;
				}
				break;
			}
		}

	} else if(s->read_bytes != NULL) {
		/* use byte-oriented read_bytes() method */

		if (s->size_known && s->size < c->start + CHUNKSIZE) {
			/* do not try to read beyond known end of file */
			toread = s->size - c->end;
			/* toread cannot be zero or negative due to the preconditions */
		} else {
			toread = CHUNKSIZE - c->len;
		}
		result = s->read_bytes(s, c->start + c->len, toread,
		                       c->buf + c->len);
		if (result > 0) {
			/* adjust offsets */
			c->len += result;
			c->end = c->start + c->len;
			if (s->sequential)
				s->seq_pos += result;
		}
		if (result < toread) {
			/* we fell short, so it must have been an error or end-of-file */
			/* make sure we don't try again */
			if (!s->size_known || s->size > c->end) {
				s->size_known = 1;
				s->size = c->end;
			}
		}
	} else {
		/* FATAL: no read functions defined!! */
		error("internal malfunction!! No read_byte|read_block callbacks defined!");
	}
	return c;
}

static CHUNK * get_chunk_alloc(CACHE *cache, U64 start) {
	int hpos;
	CHUNK *chain, *trav, *c;

	/* get hash bucket (chain) */
	hpos = HASHFUNC(start);
	chain = cache->hashtab[hpos];

	if (chain == NULL) {
		/* bucket is empty, allocate new chunk */
		c = (CHUNK *)malloc(sizeof(CHUNK));
		if (c == NULL)
			bailout("Out of memory");
		c->buf = malloc(CHUNKSIZE);
		if (c->buf == NULL)
			bailout("Out of memory");
		c->start = start;
		c->end = start;
		c->len = 0;
		/* create a new ring list */
		c->prev = c->next = c;
		cache->hashtab[hpos] = c;
		return c;
	}

	/* travel the ring list, looking for the wanted chunk */
	trav = chain;
	do {
		if (trav->start == start)  /* found existing chunk */
			return trav;
		trav = trav->next;
	} while (trav != chain);

	/* not found, allocate new chunk */
	c = (CHUNK *)malloc(sizeof(CHUNK));
	if (c == NULL)
		bailout("Out of memory");
	c->buf = malloc(CHUNKSIZE);
	if (c->buf == NULL)
		bailout("Out of memory");
	c->start = start;
	c->end = start;
	c->len = 0;
	/* add to ring list before chain, becomes new head */
	c->prev = chain->prev;
	c->next = chain;
	c->prev->next = c;
	c->next->prev = c;
	cache->hashtab[hpos] = c;
	return c;
}

/*
 * dispose of a source
 */

void close_source(SOURCE *s) {
	CACHE *cache;
	int hpos;
	CHUNK *chain, *trav, *nexttrav;

	/* drop the cache */
	cache = (CACHE *)s->cache_head;
	if (cache != NULL) {
#if PROFILE
		printf("Cache profile:\n");
#endif

		if (cache->tempbuf != NULL)
			free(cache->tempbuf);
		for (hpos = 0; hpos < HASHSIZE; hpos++) {
#if PROFILE
			printf(" hash position %d:", hpos);
#endif

			chain = cache->hashtab[hpos];
			if (chain != NULL) {
				trav = chain;
				do {
#if PROFILE
					printf(" %lluK", trav->start >> 10);
					if (trav->len != CHUNKSIZE)
						printf(":%llu", trav->len);
#endif

					nexttrav = trav->next;
					free(trav->buf);
					free(trav);
					trav = nexttrav;
				} while (trav != chain);
#if PROFILE

				printf("\n");
#endif

			}
#if PROFILE
			else
				printf(" empty\n");
#endif

		}
	}

	/* type-specific cleanup */
	if (s->close != NULL)
		(*s->close)(s);

	/* release memory for the structure */
	free(s);
}

/* EOF */