ufdt_node_pool.c

/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "ufdt_node_pool.h"

#include "libufdt_sysdeps.h"
#include "ufdt_types.h"

/* Define DEBUG_DISABLE_POOL to use dto_malloc and dto_free directly */
/* #define DEBUG_DISABLE_POOL */

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define UFDT_NODE_POOL_ENTRIES_PER_BLOCK 1024
/* UFDT_NODE_POOL_ENTRY_SIZE must be equal to or larger than
   sizeof(struct ufdt_node_fdt_node) and sizeof(struct ufdt_node_fdt_prop) */
#define UFDT_NODE_POOL_ENTRY_SIZE \
  MAX(sizeof(struct ufdt_node_fdt_node), sizeof(struct ufdt_node_fdt_prop))
/* A block is a header appended UFDT_NODE_POOL_ENTRIES_PER_BLOCK entries */
#define UFDT_NODE_POOL_BLOCK_SIZE               \
  (sizeof(struct ufdt_node_pool_block_header) + \
   UFDT_NODE_POOL_ENTRY_SIZE * UFDT_NODE_POOL_ENTRIES_PER_BLOCK)

/*
 * The data structure:
 *
 *        pool                   block                     block
 *  +--------------+     +--------------------+     +-----------------+
 *  | *first_block |---->| block_header:      |     | ...             | ...
 *  | ...          |     |  *next_block       |---->|                 |---->
 *  +--------------+     |  *first_free_entry |--\  | ...             |
 *                       |  ...               |  |
 *                       +--------------------+  |
 *                       | entry_header:      |<-/
 *                       |  *next             |--\
 *                       +--------------------+  |
 *                       |  ...               |<-/
 *                       |                    |--\
 *                       +--------------------+  |
 *                       |  ...               |  v
 */

struct ufdt_node_pool_entry_header {
  struct ufdt_node_pool_entry_header *next;
};

struct ufdt_node_pool_block_header {
  struct ufdt_node_pool_block_header *next_block;
  struct ufdt_node_pool_entry_header *first_free_entry;
  int alloc_entry_cnt;
};

void ufdt_node_pool_construct(struct ufdt_node_pool *pool) {
  pool->first_block = NULL;
  pool->last_block_ptr = &pool->first_block;
}

void ufdt_node_pool_destruct(struct ufdt_node_pool *pool) {
  int is_leak = 0;
  struct ufdt_node_pool_block_header *block = pool->first_block;
  while (block != NULL) {
    if (block->alloc_entry_cnt != 0) is_leak = 1;

    struct ufdt_node_pool_block_header *next_block = block->next_block;
    dto_free(block);
    block = next_block;
  }

  if (is_leak) {
    dto_error("Some nodes aren't freed before ufdt_node_pool_destruct().\n");
  }

  pool->first_block = NULL;
  pool->last_block_ptr = NULL;
}

static struct ufdt_node_pool_block_header *_ufdt_node_pool_create_block() {
  char *block_buf = (char *)dto_malloc(UFDT_NODE_POOL_BLOCK_SIZE);
  char *block_buf_start = block_buf + sizeof(struct ufdt_node_pool_block_header);
  char *block_buf_end = block_buf + UFDT_NODE_POOL_BLOCK_SIZE;

  struct ufdt_node_pool_block_header *block =
      (struct ufdt_node_pool_block_header *)block_buf;

  // Setup all entries to be a one way link list
  struct ufdt_node_pool_entry_header **next_ptr = &block->first_free_entry;
  for (char *entry_buf = block_buf_start; entry_buf < block_buf_end;
       entry_buf += UFDT_NODE_POOL_ENTRY_SIZE) {
    struct ufdt_node_pool_entry_header *entry =
        (struct ufdt_node_pool_entry_header *)entry_buf;

    *next_ptr = entry;

    next_ptr = &entry->next;
  }
  *next_ptr = NULL;

  block->next_block = NULL;
  block->alloc_entry_cnt = 0;

  return block;
}

static void _ufdt_node_pool_destory_block(
    struct ufdt_node_pool_block_header *block) {
  dto_free(block);
}

static void *_ufdt_node_pool_block_alloc(
    struct ufdt_node_pool_block_header *block) {
  // take the first free enrtry
  struct ufdt_node_pool_entry_header *entry = block->first_free_entry;

  block->first_free_entry = entry->next;
  block->alloc_entry_cnt++;

  return entry;
}

static void _ufdt_node_pool_block_free(struct ufdt_node_pool_block_header *block,
                                       void *node) {
  // put the node to the first free enrtry
  struct ufdt_node_pool_entry_header *entry = node;
  entry->next = block->first_free_entry;

  block->first_free_entry = entry;
  block->alloc_entry_cnt--;
}

static void _ufdt_node_pool_preppend_block(
    struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
  struct ufdt_node_pool_block_header *origin_first_block = pool->first_block;
  block->next_block = origin_first_block;

  pool->first_block = block;
  if (origin_first_block == NULL) {
    pool->last_block_ptr = &block->next_block;
  }
}

static void _ufdt_node_pool_append_block(
    struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
  block->next_block = NULL;

  *pool->last_block_ptr = block;
  pool->last_block_ptr = &block->next_block;
}

static void _ufdt_node_pool_remove_block(
    struct ufdt_node_pool *pool,
    struct ufdt_node_pool_block_header **block_ptr) {
  struct ufdt_node_pool_block_header *block = *block_ptr;
  struct ufdt_node_pool_block_header *next_block = block->next_block;

  *block_ptr = next_block;
  if (next_block == NULL) {
    pool->last_block_ptr = block_ptr;
  }

  block->next_block = NULL;
}

void *ufdt_node_pool_alloc(struct ufdt_node_pool *pool) {
#ifdef DEBUG_DISABLE_POOL
  return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE);
#endif

  // return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE);
  // If there is no free block, create a new one
  struct ufdt_node_pool_block_header *block = pool->first_block;
  if (block == NULL || block->first_free_entry == NULL) {
    block = _ufdt_node_pool_create_block();
    _ufdt_node_pool_preppend_block(pool, block);
  }

  void *node = _ufdt_node_pool_block_alloc(block);

  // Move the block to the last if there is no free entry
  if (block->first_free_entry == NULL && *pool->last_block_ptr != block) {
    _ufdt_node_pool_remove_block(pool, &pool->first_block);
    _ufdt_node_pool_append_block(pool, block);
  }

  return node;
}

static struct ufdt_node_pool_block_header **_ufdt_node_pool_search_block(
    struct ufdt_node_pool *pool, void *node) {
  struct ufdt_node_pool_block_header **block_ptr = &pool->first_block;
  while (*block_ptr != NULL) {
    struct ufdt_node_pool_block_header *block = *block_ptr;
    const char *block_buf_start =
        (char *)block + sizeof(struct ufdt_node_pool_block_header);
    const char *block_buf_end = (char *)block + UFDT_NODE_POOL_BLOCK_SIZE;

    if ((char *)node >= block_buf_start && (char *)node < block_buf_end) {
      break;
    }

    block_ptr = &block->next_block;
  }
  return block_ptr;
}

void ufdt_node_pool_free(struct ufdt_node_pool *pool, void *node) {
#ifdef DEBUG_DISABLE_POOL
  return dto_free(node);
#endif

  struct ufdt_node_pool_block_header **block_ptr =
      _ufdt_node_pool_search_block(pool, node);
  if (*block_ptr == NULL) {
    dto_error("Given node is not in the pool.\n");
    return;
  }

  struct ufdt_node_pool_block_header *block = *block_ptr;
  _ufdt_node_pool_block_free(block, node);
  _ufdt_node_pool_remove_block(pool, block_ptr);

  /* Delay free block: free the block only if the block is all freed and
      there has at least one another free block */
  if (block->alloc_entry_cnt == 0 && pool->first_block != NULL &&
      pool->first_block->first_free_entry != NULL) {
    _ufdt_node_pool_destory_block(block);
    return;
  }

  _ufdt_node_pool_preppend_block(pool, block);
}