PerformanceTests/JetStream2/wasm/TSF/tsf_region.h - WebKit - Git at Google

 /*
  * Copyright (C) 2003, 2004, 2005, 2014, 2015 Filip Pizlo. All rights reserved.
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY FILIP PIZLO ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL FILIP PIZLO OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 /*
  * Region memory management API specifically for complex objects that consist of lots of
  * small chunks of memory. This code will compile as both C and C++.
  */

 #ifndef FP_TSF_REGION_H
 #define FP_TSF_REGION_H

 #include "tsf_config.h"
 #include "tsf_types.h"

 #include <string.h>
 #include <stdlib.h>

 /* private stuff */
 #define TSF_ALIGN(size) \
     ((size + TSF_NATIVE_ALIGNMENT - 1) & (~(TSF_NATIVE_ALIGNMENT - 1)))

 /* the following invariant must hold: TSF_REGION_SIZE_BITS < 16 */
 #define TSF_REGION_SIZE_BITS 10
 #define TSF_REGION_SIZE_UNIT (1 << TSF_REGION_SIZE_BITS)

 /* only pass an aligned size */
 #define TSF_SIZE_FOR_REGION(size_needed) \
     ((size_needed + TSF_REGION_SIZE_UNIT - 1) & ~(TSF_REGION_SIZE_UNIT - 1))
 #define TSF_INITIAL_SIZE_FOR_REGION(size_needed) \
     TSF_SIZE_FOR_REGION(size_needed)

 struct tsf_region;
 struct tsf_region_cback_node;
 typedef struct tsf_region tsf_region_t;
 typedef struct tsf_region_cback_node tsf_region_cback_node_t;

 typedef void (*tsf_region_cback_t)(void *arg);

 struct tsf_region_cback_node {
     tsf_region_cback_t cback;
     void *arg;
     tsf_region_cback_node_t *next;
 };

 struct tsf_region {
     tsf_region_t *next;
     uint8_t *alloc;
     size_t size;

     tsf_region_cback_node_t *cback_head;

     /* wanna make this structure native aligned. */
 #if (((NATIVE_ALIGNMENT -                       \
        (SIZEOF_VOID_P * 3 + SIZEOF_SIZE_T)) &   \
       (NATIVE_ALIGNMENT - 1)) != 0)
     char padding[(TSF_NATIVE_ALIGNMENT -
                   (TSF_SIZEOF_VOID_P * 3 + TSF_SIZEOF_SIZE_T))
                  & (TSF_NATIVE_ALIGNMENT - 1)];
 #endif
 };

 static TSF_inline void *tsf_region_create(size_t size) {
     size_t region_size;
     tsf_region_t *region;

     size = TSF_ALIGN(size);
     region_size = TSF_INITIAL_SIZE_FOR_REGION(size);

     /* start a new region and allocate the root object */

     region = (tsf_region_t*)
         malloc(sizeof(tsf_region_t) + region_size);
     if (region == NULL) {
         return NULL;
     }

     region->next = region;
     region->alloc = ((uint8_t*)(region + 1)) + size;
     region->size = region_size;
     region->cback_head = NULL;

     return region + 1;
 }

 static TSF_inline void *tsf_region_alloc(void *root,
                                          size_t size) {
     tsf_region_t *region;
     tsf_region_t *next;
     void *result;

     size = TSF_ALIGN(size);

     region = ((tsf_region_t*)root) - 1;
     next = region->next;

     /* allocate new object */

     /* we do the comparison this way to avoid overflow! */
     if (next->alloc - ((uint8_t*)next) - sizeof(tsf_region_t) + size > next->size) {
         /* alloc new chunk */

         tsf_region_t *new_chunk = (tsf_region_t*)
             malloc(sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

         if (new_chunk == NULL) {
             return NULL;
         }

         new_chunk->next = next;
         new_chunk->alloc = (uint8_t*)(new_chunk + 1);
         new_chunk->size = TSF_SIZE_FOR_REGION(size);
         next=region->next = new_chunk;
     }

     result = next->alloc;
     next->alloc += size;
     return result;
 }

 static TSF_inline char *tsf_region_strdup(void *root,
                                           const char *str) {
     size_t size;
     char *result;

     size = strlen(str) + 1;
     result = (char*)tsf_region_alloc(root, size);
     if (result == NULL) {
         return NULL;
     }

     memcpy(result, str, size);

     return result;
 }

 static TSF_inline void *tsf_region_realloc(void *root,
                                            void *obj,
                                            size_t size) {
     tsf_region_t *region;
     tsf_region_t *next;

     size = TSF_ALIGN(size);

     region = ((tsf_region_t*)root) - 1;
     next = region->next;

     /* resize an existing object */

     /* we do the comparison this way to avoid overflow! */
     if (((uint8_t*)obj) - ((uint8_t*)next) - sizeof(tsf_region_t) + size >
         next->size) {

         /* check if this is the only object in the chunk. */
         if (next + 1 == obj) {
             /* if so, simply realloc the chunk.  we do this to prevent
              * O(n^2) memory usage in the case of repeated reallocs. */

             next = (tsf_region_t*)
                 realloc(next,
                         sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

             if (next == NULL) {
                 return NULL;
             }
         } else {
             /* alloc new chunk */

             tsf_region_t *new_chunk = (tsf_region_t*)
                 malloc(sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

             if (new_chunk == NULL) {
                 return NULL;
             }

             new_chunk->next = next;
             new_chunk->size = TSF_SIZE_FOR_REGION(size);

             memcpy(new_chunk + 1, obj, next->alloc - ((uint8_t*)obj));

             next = new_chunk;
         }

         region->next = next;
         obj = next + 1;
     }

     next->alloc = ((uint8_t*)obj) + size;
     return obj;
 }

 /* allocate either in a region or using straight malloc.  will use
  * malloc if region is NULL, otherwise will call tsf_region_alloc.()
  * this cannot create a new region.  this is useful as a convenience
  * function for implementing data structures that need to be used both
  * in a region and with malloc & free. */
 static TSF_inline void *tsf_cond_alloc(void *root, size_t size) {
     if (root == NULL) {
         return malloc(size);
     }
     return tsf_region_alloc(root, size);
 }

 /* reallocate either in a region or using straight malloc. */
 static TSF_inline void *tsf_cond_realloc(void *root, void *ptr, size_t size) {
     if (root == NULL) {
         return realloc(ptr, size);
     }
     return tsf_region_realloc(root, ptr, size);
 }

 static TSF_inline tsf_bool_t tsf_region_add_cback(void *root,
                                                   tsf_region_cback_t cback,
                                                   void *arg) {
     tsf_region_t *region = ((tsf_region_t*)root) - 1;

     tsf_region_cback_node_t *node = (tsf_region_cback_node_t*)
         tsf_region_alloc(root, sizeof(tsf_region_cback_node_t));
     if (node == NULL) {
         return tsf_false;
     }

     node->next = region->cback_head;
     node->cback = cback;
     node->arg = arg;

     region->cback_head = node;

     return tsf_true;
 }

 /* delete a region rooted at the given object. */
 static TSF_inline void tsf_region_free(void *root) {
     tsf_region_t *cur = ((tsf_region_t*)root) - 1;
     tsf_region_cback_node_t *cback_node = cur->cback_head;
     while (cback_node != NULL) {
         cback_node->cback(cback_node->arg);
         cback_node = cback_node->next;
     }
     do {
         tsf_region_t *to_free = cur;
         cur = cur->next;
         free(to_free);
     } while (cur+1 != root);
 }

 /* get the total allocatable space occupied by this region */
 static TSF_inline size_t tsf_region_size(void *root) {
     tsf_region_t *cur = ((tsf_region_t*)root) - 1;
     size_t result = 0;
     do {
         result += cur->size;
         cur = cur->next;
     } while (cur + 1 != root);
     return result;
 }

 #endif
	/*
	* Copyright (C) 2003, 2004, 2005, 2014, 2015 Filip Pizlo. All rights reserved.
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY FILIP PIZLO ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL FILIP PIZLO OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	/*
	* Region memory management API specifically for complex objects that consist of lots of
	* small chunks of memory. This code will compile as both C and C++.
	*/

	#ifndef FP_TSF_REGION_H
	#define FP_TSF_REGION_H

	#include "tsf_config.h"
	#include "tsf_types.h"

	#include <string.h>
	#include <stdlib.h>

	/* private stuff */
	#define TSF_ALIGN(size) \
	((size + TSF_NATIVE_ALIGNMENT - 1) & (~(TSF_NATIVE_ALIGNMENT - 1)))

	/* the following invariant must hold: TSF_REGION_SIZE_BITS < 16 */
	#define TSF_REGION_SIZE_BITS 10
	#define TSF_REGION_SIZE_UNIT (1 << TSF_REGION_SIZE_BITS)

	/* only pass an aligned size */
	#define TSF_SIZE_FOR_REGION(size_needed) \
	((size_needed + TSF_REGION_SIZE_UNIT - 1) & ~(TSF_REGION_SIZE_UNIT - 1))
	#define TSF_INITIAL_SIZE_FOR_REGION(size_needed) \
	TSF_SIZE_FOR_REGION(size_needed)

	struct tsf_region;
	struct tsf_region_cback_node;
	typedef struct tsf_region tsf_region_t;
	typedef struct tsf_region_cback_node tsf_region_cback_node_t;

	typedef void (tsf_region_cback_t)(void arg);

	struct tsf_region_cback_node {
	tsf_region_cback_t cback;
	void *arg;
	tsf_region_cback_node_t *next;
	};

	struct tsf_region {
	tsf_region_t *next;
	uint8_t *alloc;
	size_t size;

	tsf_region_cback_node_t *cback_head;

	/* wanna make this structure native aligned. */
	#if (((NATIVE_ALIGNMENT - \
	(SIZEOF_VOID_P * 3 + SIZEOF_SIZE_T)) & \
	(NATIVE_ALIGNMENT - 1)) != 0)
	char padding[(TSF_NATIVE_ALIGNMENT -
	(TSF_SIZEOF_VOID_P * 3 + TSF_SIZEOF_SIZE_T))
	& (TSF_NATIVE_ALIGNMENT - 1)];
	#endif
	};

	static TSF_inline void *tsf_region_create(size_t size) {
	size_t region_size;
	tsf_region_t *region;

	size = TSF_ALIGN(size);
	region_size = TSF_INITIAL_SIZE_FOR_REGION(size);

	/* start a new region and allocate the root object */

	region = (tsf_region_t*)
	malloc(sizeof(tsf_region_t) + region_size);
	if (region == NULL) {
	return NULL;
	}

	region->next = region;
	region->alloc = ((uint8_t*)(region + 1)) + size;
	region->size = region_size;
	region->cback_head = NULL;

	return region + 1;
	}

	static TSF_inline void tsf_region_alloc(void root,
	size_t size) {
	tsf_region_t *region;
	tsf_region_t *next;
	void *result;

	size = TSF_ALIGN(size);

	region = ((tsf_region_t*)root) - 1;
	next = region->next;

	/* allocate new object */

	/* we do the comparison this way to avoid overflow! */
	if (next->alloc - ((uint8_t*)next) - sizeof(tsf_region_t) + size > next->size) {
	/* alloc new chunk */

	tsf_region_t new_chunk = (tsf_region_t)
	malloc(sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

	if (new_chunk == NULL) {
	return NULL;
	}

	new_chunk->next = next;
	new_chunk->alloc = (uint8_t*)(new_chunk + 1);
	new_chunk->size = TSF_SIZE_FOR_REGION(size);
	next=region->next = new_chunk;
	}

	result = next->alloc;
	next->alloc += size;
	return result;
	}

	static TSF_inline char tsf_region_strdup(void root,
	const char *str) {
	size_t size;
	char *result;

	size = strlen(str) + 1;
	result = (char*)tsf_region_alloc(root, size);
	if (result == NULL) {
	return NULL;
	}

	memcpy(result, str, size);

	return result;
	}

	static TSF_inline void tsf_region_realloc(void root,
	void *obj,
	size_t size) {
	tsf_region_t *region;
	tsf_region_t *next;

	size = TSF_ALIGN(size);

	region = ((tsf_region_t*)root) - 1;
	next = region->next;

	/* resize an existing object */

	/* we do the comparison this way to avoid overflow! */
	if (((uint8_t)obj) - ((uint8_t)next) - sizeof(tsf_region_t) + size >
	next->size) {

	/* check if this is the only object in the chunk. */
	if (next + 1 == obj) {
	/* if so, simply realloc the chunk. we do this to prevent
	* O(n^2) memory usage in the case of repeated reallocs. */

	next = (tsf_region_t*)
	realloc(next,
	sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

	if (next == NULL) {
	return NULL;
	}
	} else {
	/* alloc new chunk */

	tsf_region_t new_chunk = (tsf_region_t)
	malloc(sizeof(tsf_region_t) + TSF_SIZE_FOR_REGION(size));

	if (new_chunk == NULL) {
	return NULL;
	}

	new_chunk->next = next;
	new_chunk->size = TSF_SIZE_FOR_REGION(size);

	memcpy(new_chunk + 1, obj, next->alloc - ((uint8_t*)obj));

	next = new_chunk;
	}

	region->next = next;
	obj = next + 1;
	}

	next->alloc = ((uint8_t*)obj) + size;
	return obj;
	}

	/* allocate either in a region or using straight malloc. will use
	* malloc if region is NULL, otherwise will call tsf_region_alloc.()
	* this cannot create a new region. this is useful as a convenience
	* function for implementing data structures that need to be used both
	* in a region and with malloc & free. */
	static TSF_inline void tsf_cond_alloc(void root, size_t size) {
	if (root == NULL) {
	return malloc(size);
	}
	return tsf_region_alloc(root, size);
	}

	/* reallocate either in a region or using straight malloc. */
	static TSF_inline void tsf_cond_realloc(void root, void *ptr, size_t size) {
	if (root == NULL) {
	return realloc(ptr, size);
	}
	return tsf_region_realloc(root, ptr, size);
	}

	static TSF_inline tsf_bool_t tsf_region_add_cback(void *root,
	tsf_region_cback_t cback,
	void *arg) {
	tsf_region_t region = ((tsf_region_t)root) - 1;

	tsf_region_cback_node_t node = (tsf_region_cback_node_t)
	tsf_region_alloc(root, sizeof(tsf_region_cback_node_t));
	if (node == NULL) {
	return tsf_false;
	}

	node->next = region->cback_head;
	node->cback = cback;
	node->arg = arg;

	region->cback_head = node;

	return tsf_true;
	}

	/* delete a region rooted at the given object. */
	static TSF_inline void tsf_region_free(void *root) {
	tsf_region_t cur = ((tsf_region_t)root) - 1;
	tsf_region_cback_node_t *cback_node = cur->cback_head;
	while (cback_node != NULL) {
	cback_node->cback(cback_node->arg);
	cback_node = cback_node->next;
	}
	do {
	tsf_region_t *to_free = cur;
	cur = cur->next;
	free(to_free);
	} while (cur+1 != root);
	}

	/* get the total allocatable space occupied by this region */
	static TSF_inline size_t tsf_region_size(void *root) {
	tsf_region_t cur = ((tsf_region_t)root) - 1;
	size_t result = 0;
	do {
	result += cur->size;
	cur = cur->next;
	} while (cur + 1 != root);
	return result;
	}

	#endif