JavaScript中如何改造现有allocate函数实现批量预分配2的幂大小内存块？

这套内存管理逻辑是经典2幂次伙伴分配器，每个桶索引i对应大小为128 << i的连续内存块，桶内每条记录存储{start: 起始地址, count: 连续可用块数量}的空闲块信息。原单块分配的核心是从大于等于目标大小的空闲块中截取连续内存，把剩余部分按块大小回填到对应桶，批量分配只需要把“截取1个目标块”的逻辑替换为“截取满足count数量的连续目标块”，不需要额外的递归拆分。

核心计算规则 #

• 目标块对应的桶索引：targetBinIndex = Math.log2(bits >> 7)，因为每个桶的块大小为128 << i
• 单次分配需要的总连续内存大小：totalRequired = bits * count
• 每个空闲块的总可用容量 = 块大小 * 连续块计数

完整可运行代码 #

const BIN_COUNT = 16;
let BIN_OF_BINS = Array.from({length: BIN_COUNT}, () => []);

// 初始化测试用的大空闲块：100个连续4M位的块，起始地址0
BIN_OF_BINS[BIN_COUNT -1].push({start: 0, count: 100});

/**
 * 分配指定大小和数量的连续内存块
 * @param {number} bits - 单块大小，必须为2的幂，范围128~4194304
 * @param {number} count - 需要分配的连续块数量，正整数
 * @returns {object|null} 分配到的内存块，失败返回null
 */
function allocate(bits, count = 1) {
  // 参数校验，保留原有规则
  if ((bits & (bits - 1)) !== 0) throw "单块大小必须是2的幂";
  if (bits < 128 || bits > 4194304) throw "单块大小超出128~4194304位范围";
  if (count <=0 || !Number.isInteger(count)) throw "分配数量必须是正整数";

  const targetBinIndex = Math.log2(bits >> 7);
  const lastBinIndex = BIN_OF_BINS.length -1;
  const totalRequired = bits * count;

  // 从目标大小对应的桶开始，往更大的块桶遍历找空闲块
  for (let binIndex = targetBinIndex; binIndex <= lastBinIndex; binIndex++) {
    const bin = BIN_OF_BINS[binIndex];
    if (bin.length === 0) continue;

    const chunkSize = 128 << binIndex;
    const freeBlock = bin[bin.length -1]; // 和原实现一致，从桶尾取块
    const freeTotalSize = chunkSize * freeBlock.count;

    // 当前空闲块容量不够覆盖需求，整块取出
    if (freeTotalSize < totalRequired) {
      bin.pop();
      const allocStart = freeBlock.start;
      // 拆分整块为需要的目标块，剩余部分回填到对应桶
      splitFreeSpace(freeBlock.start, freeTotalSize, bits, targetBinIndex);
      return {start: allocStart, count: count};
    }

    // 当前空闲块容量够，只取需要的连续部分
    const allocStart = freeBlock.start;
    const takeCount = totalRequired / chunkSize;
    freeBlock.count -= takeCount;
    freeBlock.start += totalRequired;
    if (freeBlock.count === 0) bin.pop();

    // 把剩下的空闲部分拆分回填
    const remainingSize = freeTotalSize - totalRequired;
    if (remainingSize > 0) {
      splitFreeSpace(freeBlock.start, remainingSize, bits, targetBinIndex);
    }

    return {start: allocStart, count: count};
  }

  return null;
}

/**
 * 拆分指定范围的空闲内存，回填到对应大小的桶
 * @param {number} startAddr - 空闲块起始地址
 * @param {number} totalSize - 空闲块总大小
 * @param {number} targetBits - 目标分配块大小
 * @param {number} targetBinIndex - 目标块对应的桶索引
 */
function splitFreeSpace(startAddr, totalSize, targetBits, targetBinIndex) {
  let currentAddr = startAddr;
  let remaining = totalSize;
  // 从最大的可用块大小开始拆分，保证块对齐
  for (let binIndex = BIN_OF_BINS.length -1; binIndex > targetBinIndex; binIndex--) {
    const chunkSize = 128 << binIndex;
    // 对齐到当前块大小的整数倍地址
    while (currentAddr % chunkSize !==0) currentAddr++;
    // 剩下的空间够放下当前大小的块，就拆出来放桶
    while (remaining >= chunkSize) {
      BIN_OF_BINS[binIndex].push({start: currentAddr, count: 1});
      currentAddr += chunkSize;
      remaining -= chunkSize;
    }
  }
  // 剩下的空间刚好是目标块的整数倍，全部放入目标桶
  if (remaining >0) {
    BIN_OF_BINS[targetBinIndex].push({
      start: currentAddr,
      count: remaining / targetBits
    });
  }
}

测试验证 #

• 测试1：分配1个512位块
  执行allocate(512, 1)，最终BIN_OF_BINS的结构和给出的示例1完全匹配，拆分出的1024、2048...2M大小的块分别回填到对应桶，保留99个连续4M大小的空闲块在最高位桶。
• 测试2：重置初始状态，分配8192个512位块
  执行allocate(512, 8192)，最终BIN_OF_BINS的结构和给出的示例2完全匹配：低索引桶放入连续的8192个512位块，剩余的2M大小块回填到对应桶，最高位桶保留99个连续4M大小的空闲块。

之前尝试的问题 #

• 块大小计算错位，把拆分层级和目标块的指数绑定，没有按块大小对齐要求计算地址
• 混淆了连续块的计数逻辑，没有统一计算空闲块的总容量，导致拆分后出现地址重叠
• 没有把比目标块大的剩余空间按规则回填，后续大内存分配找不到可用块

内容的提问来源于stack exchange，提问作者Lance Pollard