tor-browser

memory.c (5522B)

---

/* Copyright 2015 Google Inc. All Rights Reserved.

  Distributed under MIT license.
  See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Algorithms for distributing the literals and commands of a metablock between
  block types and contexts. */

#include "memory.h"

#include "../common/platform.h"

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

#define MAX_NEW_ALLOCATED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 2)
#define MAX_NEW_FREED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 2)
#define MAX_PERM_ALLOCATED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 1)

#define PERM_ALLOCATED_OFFSET 0
#define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED
#define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED)

void BrotliInitMemoryManager(
   MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,
   void* opaque) {
 if (!alloc_func) {
   m->alloc_func = BrotliDefaultAllocFunc;
   m->free_func = BrotliDefaultFreeFunc;
   m->opaque = 0;
 } else {
   m->alloc_func = alloc_func;
   m->free_func = free_func;
   m->opaque = opaque;
 }
#if !defined(BROTLI_ENCODER_EXIT_ON_OOM)
 m->is_oom = BROTLI_FALSE;
 m->perm_allocated = 0;
 m->new_allocated = 0;
 m->new_freed = 0;
#endif  /* BROTLI_ENCODER_EXIT_ON_OOM */
}

#if defined(BROTLI_ENCODER_EXIT_ON_OOM)

void* BrotliAllocate(MemoryManager* m, size_t n) {
 void* result = m->alloc_func(m->opaque, n);
 if (!result) exit(EXIT_FAILURE);
 return result;
}

void BrotliFree(MemoryManager* m, void* p) {
 m->free_func(m->opaque, p);
}

void BrotliWipeOutMemoryManager(MemoryManager* m) {
 BROTLI_UNUSED(m);
}

#else  /* BROTLI_ENCODER_EXIT_ON_OOM */

static void SortPointers(void** items, const size_t n) {
 /* Shell sort. */
 /* TODO(eustas): fine-tune for "many slots" case */
 static const size_t gaps[] = {23, 10, 4, 1};
 int g = 0;
 for (; g < 4; ++g) {
   size_t gap = gaps[g];
   size_t i;
   for (i = gap; i < n; ++i) {
     size_t j = i;
     void* tmp = items[i];
     for (; j >= gap && tmp < items[j - gap]; j -= gap) {
       items[j] = items[j - gap];
     }
     items[j] = tmp;
   }
 }
}

static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) {
 size_t a_read_index = 0;
 size_t b_read_index = 0;
 size_t a_write_index = 0;
 size_t b_write_index = 0;
 size_t annihilated = 0;
 while (a_read_index < a_len && b_read_index < b_len) {
   if (a[a_read_index] == b[b_read_index]) {
     a_read_index++;
     b_read_index++;
     annihilated++;
   } else if (a[a_read_index] < b[b_read_index]) {
     a[a_write_index++] = a[a_read_index++];
   } else {
     b[b_write_index++] = b[b_read_index++];
   }
 }
 while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++];
 while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++];
 return annihilated;
}

static void CollectGarbagePointers(MemoryManager* m) {
 size_t annihilated;
 SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated);
 SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed);
 annihilated = Annihilate(
     m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated,
     m->pointers + NEW_FREED_OFFSET, m->new_freed);
 m->new_allocated -= annihilated;
 m->new_freed -= annihilated;

 if (m->new_freed != 0) {
   annihilated = Annihilate(
       m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated,
       m->pointers + NEW_FREED_OFFSET, m->new_freed);
   m->perm_allocated -= annihilated;
   m->new_freed -= annihilated;
   BROTLI_DCHECK(m->new_freed == 0);
 }

 if (m->new_allocated != 0) {
   BROTLI_DCHECK(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED);
   memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated,
          m->pointers + NEW_ALLOCATED_OFFSET,
          sizeof(void*) * m->new_allocated);
   m->perm_allocated += m->new_allocated;
   m->new_allocated = 0;
   SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated);
 }
}

void* BrotliAllocate(MemoryManager* m, size_t n) {
 void* result = m->alloc_func(m->opaque, n);
 if (!result) {
   m->is_oom = BROTLI_TRUE;
   return NULL;
 }
 if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m);
 m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result;
 return result;
}

void BrotliFree(MemoryManager* m, void* p) {
 if (!p) return;
 m->free_func(m->opaque, p);
 if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m);
 m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p;
}

void BrotliWipeOutMemoryManager(MemoryManager* m) {
 size_t i;
 CollectGarbagePointers(m);
 /* Now all unfreed pointers are in perm-allocated list. */
 for (i = 0; i < m->perm_allocated; ++i) {
   m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]);
 }
 m->perm_allocated = 0;
}

#endif  /* BROTLI_ENCODER_EXIT_ON_OOM */

void* BrotliBootstrapAlloc(size_t size,
   brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
 if (!alloc_func && !free_func) {
   return malloc(size);
 } else if (alloc_func && free_func) {
   return alloc_func(opaque, size);
 }
 return NULL;
}

void BrotliBootstrapFree(void* address, MemoryManager* m) {
 if (!address) {
   /* Should not happen! */
   return;
 } else {
   /* Copy values, as those would be freed. */
   brotli_free_func free_func = m->free_func;
   void* opaque = m->opaque;
   free_func(opaque, address);
 }
}

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif