From b7b65090b29e6bc133c7922f8290c1e2f75b064a Mon Sep 17 00:00:00 2001 From: Simon Glass Date: Sun, 8 Nov 2015 23:47:47 -0700 Subject: [PATCH] Add a circular memory buffer implementation This will be used to support console recording. It provides for a circular buffer which can be written at the head and read from the tail. It supports avoiding data copying by providing raw access to the data. Signed-off-by: Simon Glass --- include/membuff.h | 246 +++++++++++++++++++++++++++++ lib/Makefile | 1 + lib/membuff.c | 390 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 637 insertions(+) create mode 100644 include/membuff.h create mode 100644 lib/membuff.c diff --git a/include/membuff.h b/include/membuff.h new file mode 100644 index 0000000000..78918e7264 --- /dev/null +++ b/include/membuff.h @@ -0,0 +1,246 @@ +/* + * Copyright (c) 2015 Google, Inc + * Written by Simon Glass + * + * Copyright (c) 1992 Simon Glass + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef _MEMBUFF_H +#define _MEMBUFF_H + +/** + * @struct membuff: holds the state of a membuff - it is used for input and + * output buffers. The buffer extends from @start to (@start + @size - 1). + * Data in the buffer extends from @tail to @head: it is written in at + * @head and read out from @tail. The membuff is empty when @head == @tail + * and full when adding another character would make @head == @tail. We + * therefore waste one character in the membuff to avoid having an extra flag + * to determine whether (when @head == @tail) the membuff is empty or full. + * + * xxxxxx data + * ...... empty + * + * .............xxxxxxxxxxxxxxxx......................... + * ^ ^ + * tail head + * + * xxxxxxxxxxxxx................xxxxxxxxxxxxxxxxxxxxxxxxx + * ^ ^ + * head tail + */ +struct membuff { + char *start; /** the start of the buffer */ + char *end; /** the end of the buffer (start + length) */ + char *head; /** current buffer head */ + char *tail; /** current buffer tail */ +}; + +/** + * membuff_purge() - reset a membuff to the empty state + * + * Initialise head and tail pointers so that the membuff becomes empty. + * + * @mb: membuff to purge + */ +void membuff_purge(struct membuff *mb); + +/** + * membuff_putraw() - find out where bytes can be written + * + * Work out where in the membuff some data could be written. Return a pointer + * to the address and the number of bytes which can be written there. If + * @update is true, the caller must then write the data immediately, since + * the membuff is updated as if the write has been done, + * + * Note that because the spare space in a membuff may not be contiguous, this + * function may not return @maxlen even if there is enough space in the + * membuff. However, by calling this function twice (with @update == true), + * you will get access to all the spare space. + * + * @mb: membuff to adjust + * @maxlen: the number of bytes we want to write + * @update: true to update the membuff as if the write happened, false to not + * @data: the address data can be written to + * @return number of bytes which can be written + */ +int membuff_putraw(struct membuff *mb, int maxlen, bool update, char **data); + +/** + * membuff_getraw() - find and return a pointer to available bytes + * + * Returns a pointer to any valid input data in the given membuff and + * optionally marks it as read. Note that not all input data may not be + * returned, since data is not necessarily contiguous in the membuff. However, + * if you call this function twice (with @update == true) you are guaranteed + * to get all available data, in at most two installments. + * + * @mb: membuff to adjust + * @maxlen: maximum number of bytes to get + * @update: true to update the membuff as if the bytes have been read (use + * false to check bytes without reading them) + * @data: returns address of data in input membuff + * @return the number of bytes available at *@data + */ +int membuff_getraw(struct membuff *mb, int maxlen, bool update, char **data); + +/** + * membuff_putbyte() - Writes a byte to a membuff + * + * @mb: membuff to adjust + * @ch: byte to write + * @return true on success, false if membuff is full + */ +bool membuff_putbyte(struct membuff *mb, int ch); + +/** + * @mb: membuff to adjust + * membuff_getbyte() - Read a byte from the membuff + * @return the byte read, or -1 if the membuff is empty + */ +int membuff_getbyte(struct membuff *mb); + +/** + * membuff_peekbyte() - check the next available byte + * + * Return the next byte which membuff_getbyte() would return, without + * removing it from the membuff. + * + * @mb: membuff to adjust + * @return the byte peeked, or -1 if the membuff is empty + */ +int membuff_peekbyte(struct membuff *mb); + +/** + * membuff_get() - get data from a membuff + * + * Copies any available data (up to @maxlen bytes) to @buff and removes it + * from the membuff. + * + * @mb: membuff to adjust + * @Buff: address of membuff to transfer bytes to + * @maxlen: maximum number of bytes to read + * @return the number of bytes read + */ +int membuff_get(struct membuff *mb, char *buff, int maxlen); + +/** + * membuff_put() - write data to a membuff + * + * Writes some data to a membuff. Returns the number of bytes added. If this + * is less than @lnehgt, then the membuff got full + * + * @mb: membuff to adjust + * @data: the data to write + * @length: number of bytes to write from 'data' + * @return the number of bytes added + */ +int membuff_put(struct membuff *mb, const char *buff, int length); + +/** + * membuff_isempty() - check if a membuff is empty + * + * @mb: membuff to check + * @return true if empty, else false + */ +bool membuff_isempty(struct membuff *mb); + +/** + * membuff_avail() - check available data in a membuff + * + * @mb: membuff to check + * @return number of bytes of data available + */ +int membuff_avail(struct membuff *mb); + +/** + * membuff_size() - get the size of a membuff + * + * Note that a membuff can only old data up to one byte less than its size. + * + * @mb: membuff to check + * @return total size + */ +int membuff_size(struct membuff *mb); + +/** + * membuff_makecontig() - adjust all membuff data to be contiguous + * + * This places all data in a membuff into a single contiguous lump, if + * possible + * + * @mb: membuff to adjust + * @return true on success + */ +bool membuff_makecontig(struct membuff *mb); + +/** + * membuff_free() - find the number of bytes that can be written to a membuff + * + * @mb: membuff to check + * @return returns the number of bytes free in a membuff + */ +int membuff_free(struct membuff *mb); + +/** + * membuff_readline() - read a line of text from a membuff + * + * Reads a line of text of up to 'maxlen' characters from a membuff and puts + * it in @str. Any character less than @minch is assumed to be the end of + * line character + * + * @mb: membuff to adjust + * @str: Place to put the line + * @maxlen: Maximum line length (excluding terminator) + * @return number of bytes read (including terminator) if a line has been + * read, 0 if nothing was there + */ +int membuff_readline(struct membuff *mb, char *str, int maxlen, int minch); + +/** + * membuff_extend_by() - expand a membuff + * + * Extends a membuff by the given number of bytes + * + * @mb: membuff to adjust + * @by: Number of bytes to increase the size by + * @max: Maximum size to allow + * @return 0 if the expand succeeded, -ENOMEM if not enough memory, -E2BIG + * if the the size would exceed @max + */ +int membuff_extend_by(struct membuff *mb, int by, int max); + +/** + * membuff_init() - set up a new membuff using an existing membuff + * + * @mb: membuff to set up + * @buff: Address of buffer + * @size: Size of buffer + */ +void membuff_init(struct membuff *mb, char *buff, int size); + +/** + * membuff_uninit() - clear a membuff so it can no longer be used + * + * @mb: membuff to uninit + */ +void membuff_uninit(struct membuff *mb); + +/** + * membuff_new() - create a new membuff + * + * @mb: membuff to init + * @size: size of membuff to create + * @return 0 if OK, -ENOMEM if out of memory + */ +int membuff_new(struct membuff *mb, int size); + +/** + * membuff_dispose() - free memory allocated to a membuff and uninit it + * + * @mb: membuff to dispose + */ +void membuff_dispose(struct membuff *mb); + +#endif diff --git a/lib/Makefile b/lib/Makefile index 3eecefaa79..6c3627847f 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -74,6 +74,7 @@ obj-y += div64.o obj-y += hang.o obj-y += linux_compat.o obj-y += linux_string.o +obj-y += membuff.o obj-$(CONFIG_REGEX) += slre.o obj-y += string.o obj-y += time.o diff --git a/lib/membuff.c b/lib/membuff.c new file mode 100644 index 0000000000..fc37757f0c --- /dev/null +++ b/lib/membuff.c @@ -0,0 +1,390 @@ +/* + * Copyright (c) 2015 Google, Inc + * Written by Simon Glass + * + * Copyright (c) 1992 Simon Glass + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include +#include +#include +#include "membuff.h" + +void membuff_purge(struct membuff *mb) +{ + /* set mb->head and mb->tail so the buffers look empty */ + mb->head = mb->start; + mb->tail = mb->start; +} + +static int membuff_putrawflex(struct membuff *mb, int maxlen, bool update, + char ***data, int *offsetp) +{ + int len; + + /* always write to 'mb->head' */ + assert(data && offsetp); + *data = &mb->start; + *offsetp = mb->head - mb->start; + + /* if there is no buffer, we can do nothing */ + if (!mb->start) + return 0; + + /* + * if head is ahead of tail, we can write from head until the end of + * the buffer + */ + if (mb->head >= mb->tail) { + /* work out how many bytes can fit here */ + len = mb->end - mb->head - 1; + if (maxlen >= 0 && len > maxlen) + len = maxlen; + + /* update the head pointer to mark these bytes as written */ + if (update) + mb->head += len; + + /* + * if the tail isn't at start of the buffer, then we can + * write one more byte right at the end + */ + if ((maxlen < 0 || len < maxlen) && mb->tail != mb->start) { + len++; + if (update) + mb->head = mb->start; + } + + /* otherwise now we can write until head almost reaches tail */ + } else { + /* work out how many bytes can fit here */ + len = mb->tail - mb->head - 1; + if (maxlen >= 0 && len > maxlen) + len = maxlen; + + /* update the head pointer to mark these bytes as written */ + if (update) + mb->head += len; + } + + /* return the number of bytes which can be/must be written */ + return len; +} + +int membuff_putraw(struct membuff *mb, int maxlen, bool update, char **data) +{ + char **datap; + int offset; + int size; + + size = membuff_putrawflex(mb, maxlen, update, &datap, &offset); + *data = *datap + offset; + + return size; +} + +bool membuff_putbyte(struct membuff *mb, int ch) +{ + char *data; + + if (membuff_putraw(mb, 1, true, &data) != 1) + return false; + *data = ch; + + return true; +} + +int membuff_getraw(struct membuff *mb, int maxlen, bool update, char **data) +{ + int len; + + /* assume for now there is no data to get */ + len = 0; + + /* + * in this case head is ahead of tail, so we must return data between + *'tail' and 'head' + */ + if (mb->head > mb->tail) { + /* work out the amount of data */ + *data = mb->tail; + len = mb->head - mb->tail; + + /* check it isn't too much */ + if (maxlen >= 0 && len > maxlen) + len = maxlen; + + /* & mark it as read from the buffer */ + if (update) + mb->tail += len; + } + + /* + * if head is before tail, then we have data between 'tail' and 'end' + * and some more data between 'start' and 'head'(which we can't + * return this time + */ + else if (mb->head < mb->tail) { + /* work out the amount of data */ + *data = mb->tail; + len = mb->end - mb->tail; + if (maxlen >= 0 && len > maxlen) + len = maxlen; + if (update) { + mb->tail += len; + if (mb->tail == mb->end) + mb->tail = mb->start; + } + } + + debug("getraw: maxlen=%d, update=%d, head=%d, tail=%d, data=%d, len=%d", + maxlen, update, (int)(mb->head - mb->start), + (int)(mb->tail - mb->start), (int)(*data - mb->start), len); + + /* return the number of bytes we found */ + return len; +} + +int membuff_getbyte(struct membuff *mb) +{ + char *data = 0; + + return membuff_getraw(mb, 1, true, &data) != 1 ? -1 : *(uint8_t *)data; +} + +int membuff_peekbyte(struct membuff *mb) +{ + char *data = 0; + + return membuff_getraw(mb, 1, false, &data) != 1 ? -1 : *(uint8_t *)data; +} + +int membuff_get(struct membuff *mb, char *buff, int maxlen) +{ + char *data = 0, *buffptr = buff; + int len = 1, i; + + /* + * do this in up to two lots(see GetRaw for why) stopping when there + * is no more data + */ + for (i = 0; len && i < 2; i++) { + /* get a pointer to the data available */ + len = membuff_getraw(mb, maxlen, true, &data); + + /* copy it into the buffer */ + memcpy(buffptr, data, len); + buffptr += len; + maxlen -= len; + } + + /* return the number of bytes read */ + return buffptr - buff; +} + +int membuff_put(struct membuff *mb, const char *buff, int length) +{ + char *data; + int towrite, i, written; + + for (i = written = 0; i < 2; i++) { + /* ask where some data can be written */ + towrite = membuff_putraw(mb, length, true, &data); + + /* and write it, updating the bytes length */ + memcpy(data, buff, towrite); + written += towrite; + buff += towrite; + length -= towrite; + } + + /* return the number of bytes written */ + return written; +} + +bool membuff_isempty(struct membuff *mb) +{ + return mb->head == mb->tail; +} + +int membuff_avail(struct membuff *mb) +{ + struct membuff copy; + int i, avail; + char *data = 0; + + /* make a copy of this buffer's control data */ + copy = *mb; + + /* now read everything out of the copied buffer */ + for (i = avail = 0; i < 2; i++) + avail += membuff_getraw(©, -1, true, &data); + + /* and return how much we read */ + return avail; +} + +int membuff_size(struct membuff *mb) +{ + return mb->end - mb->start; +} + +bool membuff_makecontig(struct membuff *mb) +{ + int topsize, botsize; + + debug("makecontig: head=%d, tail=%d, size=%d", + (int)(mb->head - mb->start), (int)(mb->tail - mb->start), + (int)(mb->end - mb->start)); + + /* + * first we move anything at the start of the buffer into the correct + * place some way along + */ + if (mb->tail > mb->head) { + /* + * the data is split into two parts, from 0 to ->head and + * from ->tail to ->end. We move the stuff from 0 to ->head + * up to make space for the other data before it + */ + topsize = mb->end - mb->tail; + botsize = mb->head - mb->start; + + /* + * must move data at bottom up by 'topsize' bytes - check if + * there's room + */ + if (mb->head + topsize >= mb->tail) + return false; + memmove(mb->start + topsize, mb->start, botsize); + debug(" - memmove(%d, %d, %d)", topsize, 0, botsize); + + /* nothing at the start, so skip that step */ + } else { + topsize = mb->head - mb->tail; + botsize = 0; + } + + /* now move data at top down to the bottom */ + memcpy(mb->start, mb->tail, topsize); + debug(" - memcpy(%d, %d, %d)", 0, (int)(mb->tail - mb->start), topsize); + + /* adjust pointers */ + mb->tail = mb->start; + mb->head = mb->start + topsize + botsize; + + debug(" - head=%d, tail=%d", (int)(mb->head - mb->start), + (int)(mb->tail - mb->start)); + + /* all ok */ + return true; +} + +int membuff_free(struct membuff *mb) +{ + return mb->end == mb->start ? 0 : + (mb->end - mb->start) - 1 - membuff_avail(mb); +} + +int membuff_readline(struct membuff *mb, char *str, int maxlen, int minch) +{ + int len; /* number of bytes read (!= string length) */ + char *s, *end; + bool ok = false; + char *orig = str; + + end = mb->head >= mb->tail ? mb->head : mb->end; + for (len = 0, s = mb->tail; s < end && len < maxlen - 1; str++) { + *str = *s++; + len++; + if (*str == '\n' || *str < minch) { + ok = true; + break; + } + if (s == end && mb->tail > mb->head) { + s = mb->start; + end = mb->head; + } + } + + /* couldn't get the whole string */ + if (!ok) { + if (maxlen) + *orig = '\0'; + return 0; + } + + /* terminate the string, update the membuff and return success */ + *str = '\0'; + mb->tail = s == mb->end ? mb->start : s; + + return len; +} + +int membuff_extend_by(struct membuff *mb, int by, int max) +{ + int oldhead, oldtail; + int size, orig; + char *ptr; + + /* double the buffer size until it is big enough */ + assert(by >= 0); + for (orig = mb->end - mb->start, size = orig; size < orig + by;) + size *= 2; + if (max != -1) + size = min(size, max); + by = size - orig; + + /* if we're already at maximum, give up */ + if (by <= 0) + return -E2BIG; + + oldhead = mb->head - mb->start; + oldtail = mb->tail - mb->start; + ptr = realloc(mb->start, size); + if (!ptr) + return -ENOMEM; + mb->start = ptr; + mb->head = mb->start + oldhead; + mb->tail = mb->start + oldtail; + + if (mb->head < mb->tail) { + memmove(mb->tail + by, mb->tail, orig - oldtail); + mb->tail += by; + } + mb->end = mb->start + size; + + return 0; +} + +void membuff_init(struct membuff *mb, char *buff, int size) +{ + mb->start = buff; + mb->end = mb->start + size; + membuff_purge(mb); +} + +int membuff_new(struct membuff *mb, int size) +{ + mb->start = malloc(size); + if (!mb->start) + return -ENOMEM; + + membuff_init(mb, mb->start, size); + return 0; +} + +void membuff_uninit(struct membuff *mb) +{ + mb->end = NULL; + mb->start = NULL; + membuff_purge(mb); +} + +void membuff_dispose(struct membuff *mb) +{ + free(&mb->start); + membuff_uninit(mb); +} -- 2.25.1