[PATCH 08/11] fs: ramfs: Use dynamically sized chunks
Ahmad Fatoum
a.fatoum at pengutronix.de
Thu Jul 2 10:28:26 EDT 2020
On 6/15/20 8:02 AM, Sascha Hauer wrote:
> This changes the way ramfs stores its data. So far we used equally sized
> chunks, this patch changes it to use chunks in a size that fits our
> needs. The chunks are always allocated in the size they are needed for
> the current truncation. Only if we fail to allocate all desired memory
> at once we fall back to allocating smaller chunks. Together with using
> the generic list implementation this results in smaller code and has
> the advantage that many image files end up being contiguously in memory
> and thus we can provide a memmap for them. Files will end up
> contiguously in memory when they are first created, then truncated to
> the final size and then filled up with data. This is something which
> is normally easily achievable when desired.
>
> Signed-off-by: Sascha Hauer <s.hauer at pengutronix.de>
> ---
> fs/ramfs.c | 307 +++++++++++++++++++++++++++--------------------------
> 1 file changed, 159 insertions(+), 148 deletions(-)
>
> diff --git a/fs/ramfs.c b/fs/ramfs.c
> index 2b6df07996..ebe03de736 100644
> --- a/fs/ramfs.c
> +++ b/fs/ramfs.c
> @@ -23,12 +23,15 @@
> #include <errno.h>
> #include <linux/stat.h>
> #include <xfuncs.h>
> +#include <linux/sizes.h>
>
> #define CHUNK_SIZE (4096 * 2)
>
> struct ramfs_chunk {
> char *data;
> - struct ramfs_chunk *next;
> + unsigned long ofs;
> + int size;
> + struct list_head list;
> };
>
> struct ramfs_inode {
> @@ -37,12 +40,14 @@ struct ramfs_inode {
> char *symlink;
> ulong mode;
>
> - ulong size;
> - struct ramfs_chunk *data;
> + /* bytes used in this inode */
> + unsigned long size;
> + /* bytes currently allocated for this inode */
> + unsigned long alloc_size;
> +
> + struct list_head data;
>
> - /* Points to recently used chunk */
> - int recent_chunk;
> - struct ramfs_chunk *recent_chunkp;
> + struct ramfs_chunk *current_chunk;
> };
>
> static inline struct ramfs_inode *to_ramfs_inode(struct inode *inode)
> @@ -89,18 +94,25 @@ static struct inode *ramfs_get_inode(struct super_block *sb, const struct inode
> return inode;
> }
>
> -static struct ramfs_chunk *ramfs_get_chunk(void)
> +#define MIN_SIZE SZ_8K
> +
> +static struct ramfs_chunk *ramfs_get_chunk(unsigned long size)
> {
> struct ramfs_chunk *data = malloc(sizeof(struct ramfs_chunk));
> +
> if (!data)
> return NULL;
>
> - data->data = calloc(CHUNK_SIZE, 1);
> + if (size < MIN_SIZE)
> + size = MIN_SIZE;
> +
> + data->data = calloc(size, 1);
> if (!data->data) {
> free(data);
> return NULL;
> }
> - data->next = NULL;
> +
> + data->size = size;
>
> return data;
> }
> @@ -160,23 +172,6 @@ static int ramfs_symlink(struct inode *dir, struct dentry *dentry,
>
> static int ramfs_unlink(struct inode *dir, struct dentry *dentry)
> {
> - struct inode *inode = d_inode(dentry);
> -
> - if (inode) {
> - struct ramfs_inode *node = to_ramfs_inode(inode);
> - struct ramfs_chunk *chunk = node->data;
> -
> - node->data = NULL;
> -
> - while (chunk) {
> - struct ramfs_chunk *tmp = chunk;
> -
> - chunk = chunk->next;
> -
> - ramfs_put_chunk(tmp);
> - }
> - }
> -
> return simple_unlink(dir, dentry);
> }
>
> @@ -200,80 +195,57 @@ static const struct inode_operations ramfs_dir_inode_operations =
> .create = ramfs_create,
> };
>
> -static struct ramfs_chunk *ramfs_find_chunk(struct ramfs_inode *node, int chunk)
> +static struct ramfs_chunk *ramfs_find_chunk(struct ramfs_inode *node,
> + unsigned long pos, int *ofs, int *len)
> {
> - struct ramfs_chunk *data;
> - int left = chunk;
> + struct ramfs_chunk *data, *cur = node->current_chunk;
>
> - if (chunk == 0)
> - return node->data;
> + if (cur && pos >= cur->ofs)
> + data = cur;
> + else
> + data = list_first_entry(&node->data, struct ramfs_chunk, list);
>
> - if (node->recent_chunk == chunk)
> - return node->recent_chunkp;
> + list_for_each_entry_from(data, &node->data, list) {
> + if (data->ofs + data->size > pos) {
> + *ofs = pos - data->ofs;
> + *len = data->ofs + data->size - pos;
>
> - if (node->recent_chunk < chunk && node->recent_chunk != 0) {
> - /* Start at last known chunk */
> - data = node->recent_chunkp;
> - left -= node->recent_chunk;
> - } else {
> - /* Start at first chunk */
> - data = node->data;
> - }
> + node->current_chunk = data;
>
> - while (left--)
> - data = data->next;
> + return data;
> + }
> + }
>
> - node->recent_chunkp = data;
> - node->recent_chunk = chunk;
> + pr_err("%s: no chunk for pos %ld found\n", __func__, pos);
>
> - return data;
> + return NULL;
> }
>
> static int ramfs_read(struct device_d *_dev, FILE *f, void *buf, size_t insize)
> {
> struct inode *inode = f->f_inode;
> struct ramfs_inode *node = to_ramfs_inode(inode);
> - int chunk;
> struct ramfs_chunk *data;
> - int ofs;
> - int now;
> - int pos = f->pos;
> + int ofs, len, now;
> + unsigned long pos = f->pos;
> int size = insize;
>
> - chunk = pos / CHUNK_SIZE;
> - debug("%s: reading from chunk %d\n", __FUNCTION__, chunk);
> + debug("%s: %p %d @ %lld\n", __func__, node, insize, f->pos);
> +
> + while (size) {
> + data = ramfs_find_chunk(node, pos, &ofs, &len);
> + if (!data)
> + return -EINVAL;
>
> - /* Position ourself in stream */
> - data = ramfs_find_chunk(node, chunk);
> - ofs = pos % CHUNK_SIZE;
> + debug("%s: pos: %ld ofs: %d len: %d\n", __func__, pos, ofs, len);
> +
> + now = min(size, len);
>
> - /* Read till end of current chunk */
> - if (ofs) {
> - now = min(size, CHUNK_SIZE - ofs);
> - debug("Reading till end of node. size: %d\n", size);
> memcpy(buf, data->data + ofs, now);
> +
> size -= now;
> - pos += now;
> buf += now;
> - if (pos > node->size)
> - node->size = now;
> - data = data->next;
> - }
> -
> - /* Do full chunks */
> - while (size >= CHUNK_SIZE) {
> - debug("do full chunk. size: %d\n", size);
> - memcpy(buf, data->data, CHUNK_SIZE);
> - data = data->next;
> - size -= CHUNK_SIZE;
> - pos += CHUNK_SIZE;
> - buf += CHUNK_SIZE;
> - }
> -
> - /* And the rest */
> - if (size) {
> - debug("do rest. size: %d\n", size);
> - memcpy(buf, data->data, size);
> + pos += now;
> }
>
> return insize;
> @@ -283,100 +255,135 @@ static int ramfs_write(struct device_d *_dev, FILE *f, const void *buf, size_t i
> {
> struct inode *inode = f->f_inode;
> struct ramfs_inode *node = to_ramfs_inode(inode);
> - int chunk;
> struct ramfs_chunk *data;
> - int ofs;
> - int now;
> - int pos = f->pos;
> + int ofs, len, now;
> + unsigned long pos = f->pos;
On 32-bit systems, you are truncating a 64-bit pos to 32-bit here. Is this intended?
> int size = insize;
>
> - chunk = f->pos / CHUNK_SIZE;
> - debug("%s: writing to chunk %d\n", __FUNCTION__, chunk);
> + debug("%s: %p %d @ %lld\n", __func__, node, insize, f->pos);
> +
> + while (size) {
> + data = ramfs_find_chunk(node, pos, &ofs, &len);
> + if (!data)
> + return -EINVAL;
> +
> + debug("%s: pos: %ld ofs: %d len: %d\n", __func__, pos, ofs, len);
>
> - /* Position ourself in stream */
> - data = ramfs_find_chunk(node, chunk);
> - ofs = f->pos % CHUNK_SIZE;
> + now = min(size, len);
>
> - /* Write till end of current chunk */
> - if (ofs) {
> - now = min(size, CHUNK_SIZE - ofs);
> - debug("writing till end of node. size: %d\n", size);
> memcpy(data->data + ofs, buf, now);
> +
> size -= now;
> - pos += now;
> buf += now;
> - if (pos > node->size)
> - node->size = now;
> - data = data->next;
> + pos += now;
> + }
> +
> + return insize;
> +}
> +
> +static void ramfs_truncate_down(struct ramfs_inode *node, unsigned long size)
> +{
> + struct ramfs_chunk *data, *tmp;
> +
> + list_for_each_entry_safe(data, tmp, &node->data, list) {
> + if (data->ofs >= size) {
> + list_del(&data->list);
> + node->alloc_size -= data->size;
> + ramfs_put_chunk(data);
> + }
> }
>
> - /* Do full chunks */
> - while (size >= CHUNK_SIZE) {
> - debug("do full chunk. size: %d\n", size);
> - memcpy(data->data, buf, CHUNK_SIZE);
> - data = data->next;
> - size -= CHUNK_SIZE;
> - pos += CHUNK_SIZE;
> - buf += CHUNK_SIZE;
> + node->current_chunk = NULL;
> +}
> +
> +static int ramfs_truncate_up(struct ramfs_inode *node, unsigned long size)
> +{
> + struct ramfs_chunk *data, *tmp;
> + LIST_HEAD(list);
> + unsigned long add = size - node->alloc_size;
> + unsigned long chunksize = add;
> + unsigned long alloc_size = 0;
> +
> + if (node->alloc_size >= size)
> + return 0;
> +
> + /*
> + * We first try to allocate all space we need in a single chunk.
> + * This may fail because of fragmented memory, so in case we cannot
> + * allocate memory we successively decrease the chunk size until
> + * we have enough allocations made.
> + */
> + while (1) {
> + unsigned long now = min(chunksize, add);
> +
> + data = ramfs_get_chunk(now);
> + if (!data) {
> + /* No luck, try with smaller chunk size */
> + chunksize >>= 1;
> +
> + /* If we do not have even 128KiB then go out */
> + if (chunksize < SZ_128K)
> + goto out;
> +
> + continue;
> + }
> +
> + data->ofs = node->alloc_size + alloc_size;
> +
> + alloc_size += data->size;
> +
> + list_add_tail(&data->list, &list);
> +
> + if (add <= data->size)
> + break;
> +
> + add -= data->size;
> }
>
> - /* And the rest */
> - if (size) {
> - debug("do rest. size: %d\n", size);
> - memcpy(data->data, buf, size);
> + list_splice_tail(&list, &node->data);
> +
> + node->alloc_size += alloc_size;
> +
> + return 0;
> +
> +out:
> + list_for_each_entry_safe(data, tmp, &list, list) {
> + list_del(&data->list);
> + ramfs_put_chunk(data);
> }
>
> - return insize;
> + return -ENOSPC;
> }
>
> static int ramfs_truncate(struct device_d *dev, FILE *f, loff_t size)
> {
> struct inode *inode = f->f_inode;
> struct ramfs_inode *node = to_ramfs_inode(inode);
> - int oldchunks, newchunks;
> - struct ramfs_chunk *data = node->data;
> -
> - newchunks = (size + CHUNK_SIZE - 1) / CHUNK_SIZE;
> - oldchunks = (node->size + CHUNK_SIZE - 1) / CHUNK_SIZE;
> -
> - if (newchunks < oldchunks) {
> - if (!newchunks)
> - node->data = NULL;
> - while (newchunks--)
> - data = data->next;
> - while (data) {
> - struct ramfs_chunk *tmp;
> - tmp = data->next;
> - ramfs_put_chunk(data);
> - data = tmp;
> - }
> - if (node->recent_chunk > newchunks)
> - node->recent_chunk = 0;
> - }
> + int ret;
>
> - if (newchunks > oldchunks) {
> - if (data) {
> - data = ramfs_find_chunk(node, oldchunks - 1);
> - } else {
> - node->data = ramfs_get_chunk();
> - if (!node->data)
> - return -ENOSPC;
> - data = node->data;
> - oldchunks = 1;
> - }
> + /*
> + * This is a malloc based filesystem, no need to support more
> + * memory than fits into unsigned long.
> + */
> + if (size > ULONG_MAX)
> + return -ENOSPC;
>
> - while (data->next)
> - data = data->next;
> + debug("%s: %p cur: %ld new: %lld alloc: %ld\n", __func__, node,
> + node->size, size, node->alloc_size);
>
> - while (newchunks > oldchunks) {
> - data->next = ramfs_get_chunk();
> - if (!data->next)
> - return -ENOSPC;
> - data = data->next;
> - oldchunks++;
> - }
> + if (size == node->size)
> + return 0;
> +
> + if (size < node->size) {
> + ramfs_truncate_down(node, size);
> + } else {
> + ret = ramfs_truncate_up(node, size);
> + if (ret)
> + return ret;
> }
> +
> node->size = size;
> +
> return 0;
> }
>
> @@ -386,6 +393,8 @@ static struct inode *ramfs_alloc_inode(struct super_block *sb)
>
> node = xzalloc(sizeof(*node));
>
> + INIT_LIST_HEAD(&node->data);
> +
> return &node->inode;
> }
>
> @@ -393,6 +402,8 @@ static void ramfs_destroy_inode(struct inode *inode)
> {
> struct ramfs_inode *node = to_ramfs_inode(inode);
>
> + ramfs_truncate_down(node, 0);
> +
> free(node);
> }
>
>
--
Pengutronix e.K. | |
Steuerwalder Str. 21 | http://www.pengutronix.de/ |
31137 Hildesheim, Germany | Phone: +49-5121-206917-0 |
Amtsgericht Hildesheim, HRA 2686 | Fax: +49-5121-206917-5555 |
More information about the barebox
mailing list