/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sw=2 et tw=80:
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef gc_MallocedBlockCache_h
#define gc_MallocedBlockCache_h

#include "ds/PointerAndUint7.h"
#include "js/AllocPolicy.h"
#include "js/Vector.h"
#include "util/Poison.h"

namespace js {
namespace gc {

// MallocedBlockCache implements a lightweight wrapper around js_malloc/js_free.
//
// Blocks are requested by ::alloc and must be returned with ::free, at which
// point the cache may decide to hold on to the block rather than hand it back
// to js_free.  Subsequent ::alloc calls may be satisfied from the cached
// blocks rather than calling js_malloc.  The mechanism is designed to be much
// cheaper than calling js_malloc/js_free directly.  One consequence is that
// there is no locking; it is essential therefore to use each cache only from
// a single thread.
//
// The intended use is for lightweight management of OOL (malloc'd) storage
// associated with WasmStructObject and WasmArrayObject.  The mechanism is
// general and potentially has other uses.  Blocks of size STEP * NUM_LISTS
// and larger are never cached, though.
//
// Request sizes are rounded up to a multiple of STEP.  There are NUM_LISTS-1
// free lists, with a "List ID" indicating the multiple of STEP stored on the
// list.  So for example, blocks of size 3 * STEP (after rounding up) are
// stored on the list with ID 3.  List ID 0 indicates blocks which are too
// large to live on any freelist.  With the default settings, this gives
// separate freelists for blocks of size 16, 32, 48, .. 496.  Blocks of size
// zero are not supported, and `lists[0]` will always be empty.
//
// Allocation of a block produces not only the block's address but also its
// List ID.  When freeing, both values must be presented, because there is
// otherwise no way for ::free to know the size of the original allocation,
// and hence which freelist it should go on.  For this reason, the ::alloc and
// ::free methods produce and take a `PointerAndUint7`, not a `void*`.
//
// Resizing of blocks is not supported.

class MallocedBlockCache {
 public:
  static const size_t STEP = 16;

  static const size_t NUM_LISTS = 32;
  // This limitation exists because allocation returns a PointerAndUint7, and
  // a List-ID value (viz, 0 .. NUM_LISTS-1) is stored in the Uint7 part.
  static_assert(NUM_LISTS <= (1 << 7));

  // list[0] must always remain empty.  List ID 0 indicates a block which
  // cannot participate in the freelist machinery because it is too large.
  //
  // list[i], for 1 <= i < NUM_LISTS, holds blocks of size i * STEP only.
  // All requests are rounded up to multiple of SIZE.
  //
  // We do not expect to be required to issue or accept blocks of size zero.
  static const size_t OVERSIZE_BLOCK_LIST_ID = 0;
  using MallocedBlockVector = Vector<void*, 0, SystemAllocPolicy>;

  MallocedBlockVector lists[NUM_LISTS];

  ~MallocedBlockCache();

  static inline size_t listIDForSize(size_t size);

  // Allocation and freeing.  Use `alloc` to allocate.  `allocSlow` is
  // `alloc`s fallback path.  Do not call it directly, since it doesn't handle
  // all cases by itself.
  [[nodiscard]] inline PointerAndUint7 alloc(size_t size);
  [[nodiscard]] MOZ_NEVER_INLINE PointerAndUint7 allocSlow(size_t size);

  inline void free(PointerAndUint7 blockAndListID);

  // Allows users to gradually hand blocks back to js_free, so as to avoid
  // space leaks in long-running scenarios.  The specified percentage of
  // blocks in each list is discarded.
  void preen(double percentOfBlocksToDiscard);

  // Return all blocks in the cache to js_free.
  void clear();

  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
};

/* static */
inline size_t MallocedBlockCache::listIDForSize(size_t size) {
  // Figure out which free list can give us a block of size `size`, after it
  // has been rounded up to a multiple of `step`.
  //
  // Example mapping for STEP = 16 and NUM_LISTS = 8, after rounding up:
  //   0 never holds any blocks (denotes "too large")
  //   1 holds blocks of size  16
  //   2 holds blocks of size  32
  //   3 holds blocks of size  48
  //   4 holds blocks of size  64
  //   5 holds blocks of size  80
  //   6 holds blocks of size  96
  //   7 holds blocks of size 112
  //
  // For a request of size n:
  // * if n == 0, fail
  // * else
  //      round n up to a multiple of STEP
  //      let i = n / STEP
  //      if i >= NUM_LISTS
  //         alloc direct from js_malloc, and return listID = 0
  //      if lists[i] is nonempty, use lists[i] and return listID = i.
  //      else
  //         let p = js_malloc(n)
  //         return p and listID = i.

  // We're never expected to handle zero-sized blocks.
  MOZ_ASSERT(size > 0);

  size = js::RoundUp(size, STEP);
  size_t i = size / STEP;
  MOZ_ASSERT(i > 0);

  if (i >= NUM_LISTS) {
    return OVERSIZE_BLOCK_LIST_ID;
  }

  return i;
}

inline PointerAndUint7 MallocedBlockCache::alloc(size_t size) {
  size_t i = listIDForSize(size);
  MOZ_ASSERT(i < NUM_LISTS);

  // Fast path: try to pull a block from the relevant list.
  if (MOZ_LIKELY(
          i != OVERSIZE_BLOCK_LIST_ID &&  // "block is small enough to cache"
          !lists[i].empty())) {           // "a cached block is available"
    // Check that i is the right list
    MOZ_ASSERT(i * STEP == js::RoundUp(size, STEP));
    void* block = lists[i].popCopy();
    return PointerAndUint7(block, i);
  }

  // Fallback path for all other cases.
  return allocSlow(size);
}

inline void MallocedBlockCache::free(PointerAndUint7 blockAndListID) {
  // This is a whole lot simpler than the ::alloc case, since we are given the
  // listId and don't have to compute it (not that we have any way to).
  void* block = blockAndListID.pointer();
  uint32_t listID = blockAndListID.uint7();
  MOZ_ASSERT(block);
  MOZ_ASSERT(listID < NUM_LISTS);
  if (MOZ_UNLIKELY(listID == OVERSIZE_BLOCK_LIST_ID)) {
    // It was too large for recycling; go straight to js_free.
    js_free(block);
    return;
  }

  // Put it back on list `listId`, first poisoning it for safety.
  memset(block, JS_NOTINUSE_TRAILER_PATTERN, listID * STEP);
  MOZ_MAKE_MEM_UNDEFINED(block, listID * STEP);
  if (MOZ_UNLIKELY(!lists[listID].append(block))) {
    // OOM'd while doing admin.  Hand it off to js_free and forget about the
    // OOM.
    js_free(block);
  }
}

}  // namespace gc
}  // namespace js

#endif  // gc_MallocedBlockCache_h