static void bufferNoSetRankSet(Buffer buffer, RankSet rankset)
{
  AVERT(Buffer, buffer);
  AVERT(RankSet, rankset);
  NOTREACHED; /* .norank */
}

static Res MVFFInit(Pool pool, ArgList args)
{
  Size extendBy = MVFF_EXTEND_BY_DEFAULT;
  Size avgSize = MVFF_AVG_SIZE_DEFAULT;
  Size align = MVFF_ALIGN_DEFAULT;
  Bool slotHigh = MVFF_SLOT_HIGH_DEFAULT;
  Bool arenaHigh = MVFF_ARENA_HIGH_DEFAULT;
  Bool firstFit = MVFF_FIRST_FIT_DEFAULT;
  MVFF mvff;
  Arena arena;
  Res res;
  void *p;
  ArgStruct arg;

  AVERT(Pool, pool);
  arena = PoolArena(pool);

  /* .arg: class-specific additional arguments; see */
  /* <design/poolmvff/#method.init> */
  /* .arg.check: we do the same checks here and in MVFFCheck */
  /* except for arenaHigh, which is stored only in the segPref. */
  
  if (ArgPick(&arg, args, MPS_KEY_EXTEND_BY))
    extendBy = arg.val.size;
  
  if (ArgPick(&arg, args, MPS_KEY_MEAN_SIZE))
    avgSize = arg.val.size;
  
  if (ArgPick(&arg, args, MPS_KEY_ALIGN))
    align = arg.val.align;

  if (ArgPick(&arg, args, MPS_KEY_MVFF_SLOT_HIGH))
    slotHigh = arg.val.b;
  
  if (ArgPick(&arg, args, MPS_KEY_MVFF_ARENA_HIGH))
    arenaHigh = arg.val.b;
  
  if (ArgPick(&arg, args, MPS_KEY_MVFF_FIRST_FIT))
    firstFit = arg.val.b;

  AVER(extendBy > 0);           /* .arg.check */
  AVER(avgSize > 0);            /* .arg.check */
  AVER(avgSize <= extendBy);    /* .arg.check */
  AVER(SizeIsAligned(align, MPS_PF_ALIGN));
  AVERT(Bool, slotHigh);
  AVERT(Bool, arenaHigh);
  AVERT(Bool, firstFit);

  mvff = Pool2MVFF(pool);

  mvff->extendBy = extendBy;
  if (extendBy < ArenaAlign(arena))
    mvff->minSegSize = ArenaAlign(arena);
  else
    mvff->minSegSize = extendBy;
  mvff->avgSize = avgSize;
  pool->alignment = align;
  mvff->slotHigh = slotHigh;
  mvff->firstFit = firstFit;

  res = ControlAlloc(&p, arena, sizeof(SegPrefStruct), FALSE);
  if (res != ResOK)
    return res;

  mvff->segPref = (SegPref)p;
  SegPrefInit(mvff->segPref);
  SegPrefExpress(mvff->segPref, arenaHigh ? SegPrefHigh : SegPrefLow, NULL);

  mvff->total = 0;
  mvff->free = 0;

  res = FreelistInit(FreelistOfMVFF(mvff), align);
  if (res != ResOK)
    goto failInit;

  res = CBSInit(CBSOfMVFF(mvff), arena, (void *)mvff, align,
                /* fastFind */ TRUE, /* zoned */ FALSE, args);
  if (res != ResOK)
    goto failInit;

  mvff->sig = MVFFSig;
  AVERT(MVFF, mvff);
  EVENT8(PoolInitMVFF, pool, arena, extendBy, avgSize, align,
         BOOL(slotHigh), BOOL(arenaHigh), BOOL(firstFit));
  return ResOK;

failInit:
  ControlFree(arena, p, sizeof(SegPrefStruct));
  return res;
}

Addr VMBase(VM vm)
{
  AVERT(VM, vm);

  return vm->base;
}

Count SplayDebugCount(SplayTree splay)
{
  AVERT(SplayTree, splay);
  return TreeDebugCount(SplayTreeRoot(splay), splay->compare, splay->nodeKey);
}

static Compare SplaySplitRev(SplayStateStruct *stateReturn,
                             SplayTree splay, TreeKey key,
                             TreeCompareFunction compare)
{
  Tree middle, leftLast, rightFirst;
  Compare cmp;

  AVERT(SplayTree, splay);
  AVER(FUNCHECK(compare));
  AVER(!SplayTreeIsEmpty(splay));
  
  leftLast = TreeEMPTY;
  rightFirst = TreeEMPTY;
  middle = SplayTreeRoot(splay);
  for (;;) {
    cmp = compare(middle, key);
    switch(cmp) {
    default:
      NOTREACHED;
      /* defensive fall-through */
    case CompareEQUAL:
      goto stop;

    case CompareLESS:
      if (!TreeHasLeft(middle))
        goto stop;
      middle = SplayZigRev(middle, &rightFirst);
      cmp = compare(middle, key);
      switch(cmp) {
      default:
        NOTREACHED;
        /* defensive fall-through */
      case CompareEQUAL:
        goto stop;
      case CompareLESS:
        if (!TreeHasLeft(middle))
          goto stop;
        middle = SplayZigZigRev(middle, &rightFirst);
        splay->updateNode(splay, TreeRight(rightFirst));
        break;
      case CompareGREATER:
        if (!TreeHasRight(middle))
          goto stop;
        middle = SplayZagRev(middle, &leftLast);
        break;
      }
      break;

    case CompareGREATER:
      if (!TreeHasRight(middle))
        goto stop;
      middle = SplayZagRev(middle, &leftLast);
      cmp = compare(middle, key);
      switch(cmp) {
      default:
        NOTREACHED;
        /* defensive fall-through */
      case CompareEQUAL:
        goto stop;
      case CompareGREATER:
        if (!TreeHasRight(middle))
          goto stop;
        middle = SplayZagZagRev(middle, &leftLast);
        splay->updateNode(splay, TreeLeft(leftLast));
        break;
      case CompareLESS:
        if (!TreeHasLeft(middle))
          goto stop;
        middle = SplayZigRev(middle, &rightFirst);
        break;
      }
      break;
    }
  }

stop:
  stateReturn->middle = middle;
  stateReturn->leftLast = leftLast;
  stateReturn->rightFirst = rightFirst;
  return cmp;
}

Align VMAlign(VM vm)
{
  AVERT(VM, vm);
  return vm->align;
}

static Bool MessageOnQueue(Message message)
{
  AVERT(Message, message);

  return !RingIsSingle(&message->queueRing);
}

static Bool SplaySplay(SplayNode *nodeReturn, SplayTree tree,
                       void *key, SplayCompareMethod compareMethod) {
    /* The sides structure avoids a boundary case in SplayLink* */
    SplayNodeStruct sides; /* rightTop and leftTop */
    SplayNode top, leftLast, rightFirst;
    Bool found;
    Compare compareTop;

    AVERT(SplayTree, tree);
    AVER(nodeReturn != NULL);
    AVER(FUNCHECK(compareMethod));

    top = SplayTreeRoot(tree); /* will be copied back at end */

    if (top == NULL) {
        *nodeReturn = NULL;
        return FALSE;
    }

    /* short-circuit case where node is already top */
    compareTop = (*compareMethod)(key, top);
    if (compareTop == CompareEQUAL) {
        *nodeReturn = top;
        return TRUE;
    }

    SplayNodeInit(&sides); /* left and right trees now NULL */
    leftLast = &sides;
    rightFirst = &sides;

    while(TRUE) {
        /* compareTop is already initialised above. */
        switch(compareTop) {

        case CompareLESS: {
            SplayNode topLeft = SplayNodeLeftChild(top);
            if (topLeft == NULL) {
                found = FALSE;
                goto assemble;
            } else {
                Compare compareTopLeft = (*compareMethod)(key, topLeft);

                switch(compareTopLeft) {

                case CompareEQUAL: {                 /* zig */
                    SplayLinkRight(&top, &rightFirst);
                    found = TRUE;
                    goto assemble;
                    } /* break; */

                case CompareLESS: {                  /* zig-zig */
                    if (SplayNodeLeftChild(topLeft) == NULL)
                        goto terminalZig;
                    SplayRotateRight(&top, tree);
                    SplayLinkRight(&top, &rightFirst);
                }
                break;

                case CompareGREATER: {               /* zig-zag */
                    if (SplayNodeRightChild(topLeft) == NULL)
                        goto terminalZig;
                    SplayLinkRight(&top, &rightFirst);
                    SplayLinkLeft(&top, &leftLast);
                }
                break;

                default: {
                    NOTREACHED;
                }
                break;
                }
            }
        }
        break;

        case CompareGREATER: {
            SplayNode topRight = SplayNodeRightChild(top);
            if (topRight == NULL) {
                found = FALSE;
                goto assemble;
            } else {
                Compare compareTopRight = (*compareMethod)(key, topRight);

                switch(compareTopRight) {

                case CompareEQUAL: {                 /* zag */
                    SplayLinkLeft(&top, &leftLast);
                    found = TRUE;
                    goto assemble;
                    } /* break; */

                case CompareGREATER: {               /* zag-zag */
                    if (SplayNodeRightChild(topRight) == NULL)
                        goto terminalZag;
                    SplayRotateLeft(&top, tree);
                    SplayLinkLeft(&top, &leftLast);
                }
                break;

                case CompareLESS: {                  /* zag-zig */
//.........这里部分代码省略.........

void SplayTreeFinish(SplayTree tree)
{
    AVERT(SplayTree, tree);
    SplayTreeSetRoot(tree, NULL);
    tree->compare = NULL;
}

static Bool BTFindResRangeHigh(Index *baseReturn, Index *limitReturn,
                               BT bt,
                               Index searchBase, Index searchLimit,
                               Count minLength,
                               Count maxLength)
{
  Bool foundRes;         /* true if a reset bit is found */
  Index resLimit;        /* limit of a candidate reset range */
  Index resIndex;        /* index of highest reset bit found */
  Index unseenLimit;     /* limit of testing so far */
  Index minBase;         /* base of minimal acceptable range */
  Index resBase;         /* base of search for a candidate range */

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVERT(BT, bt);
  AVER(searchBase < searchLimit);
  AVER(minLength > 0);
  AVER(minLength <= maxLength);
  AVER(maxLength <= searchLimit - searchBase);

  foundRes = FALSE;     /* don't know first reset bit */
  minBase = 0;          /* avoid spurious compiler warning */
  resLimit = searchLimit;    /* haven't seen anything yet */
  unseenLimit = searchLimit; /* haven't seen anything yet */
  resBase = searchBase + minLength -1;

  while (resLimit > resBase) {
    Index setIndex;  /* index of first set bit found */
    Bool foundSet = FALSE; /* true if a set bit is found */

    /* Find the first reset bit if it's not already known */
    if (!foundRes) {
      /* Look for the limit of a range */
      BTFindResHigh(&foundRes, &resIndex, bt, resBase, unseenLimit);
      if (!foundRes) {
        /* failure */
        return FALSE;
      }
      resLimit = resIndex + 1;
      unseenLimit = resIndex;
      minBase = resLimit - minLength;
    }

    /* Look to see if there is any set bit in the minimum range */
    BTFindSet(&foundSet, &setIndex, bt, minBase, unseenLimit);
    if (!foundSet) {
      /* Found minimum range. Extend it. */
      Index setBase;   /* base of search for set bit */
      Index setLimit;  /* limit search for set bit */
      Index baseIndex; /* base of reset range found */
      foundSet = FALSE;
      setLimit = minBase;
      if ((searchBase + maxLength) > resLimit)
        setBase = searchBase;
      else
        setBase  = resLimit - maxLength;
      if (setLimit > setBase)
        BTFindSetHigh(&foundSet, &setIndex, bt, setBase, setLimit);
      if (foundSet)
        baseIndex = setIndex+1;
      else
        baseIndex = setBase;
     
      AVER(resLimit - baseIndex >= minLength);
      AVER(resLimit - baseIndex <= maxLength);
      *baseReturn = baseIndex;
      *limitReturn = resLimit;
      return TRUE;
     
    } else {
      /* Range was too small. Try again */
      unseenLimit = minBase;
      resLimit = setIndex;
      if (resLimit != minBase) {
        /* Already found the start of next candidate range. This wraps
         * round if minLength > resLimit (all the variables are
         * unsigned so this behaviour is defined), but that means that
         * resLimit <= resBase and so the loop will exit. */
        AVER(resLimit >= minLength || resLimit <= resBase);
        minBase = resLimit - minLength;
      } else {
        foundRes = FALSE;
      }
    }
  }

  /* failure */
  return FALSE;
}

static void SplayAssemble(SplayTree tree, SplayNode top,
                          SplayNode leftTop, SplayNode leftLast,
                          SplayNode rightTop, SplayNode rightFirst) {
    AVERT(SplayTree, tree);
    AVERT(SplayNode, top);
    AVER(leftTop == NULL ||
         (SplayNodeCheck(leftTop) && SplayNodeCheck(leftLast)));
    AVER(rightTop == NULL ||
         (SplayNodeCheck(rightTop) && SplayNodeCheck(rightFirst)));

    if (leftTop != NULL) {
        SplayNodeSetRightChild(leftLast, SplayNodeLeftChild(top));
        SplayNodeSetLeftChild(top, leftTop);

        if (tree->updateNode != NULL) {
            /* Update client property using pointer reversal (Ugh!). */
            SplayNode node, parent, rightChild;

            /* Reverse the pointers between leftTop and leftLast */
            /* leftLast is not reversed. */
            node = leftTop;
            parent = NULL;
            while(node != leftLast) {
                rightChild = SplayNodeRightChild(node);
                SplayNodeSetRightChild(node, parent); /* pointer reversal */
                parent = node;
                node = rightChild;
            }

            /* Now restore the pointers, updating the client property. */
            /* node is leftLast, parent is the last parent (or NULL). */
            SplayNodeUpdate(tree, node);
            while(node != leftTop) {
                rightChild = node;
                node = parent;
                parent = SplayNodeRightChild(node);
                SplayNodeSetRightChild(node, rightChild); /* un-reverse pointer */
                SplayNodeUpdate(tree, node);
            }
        }
    }
    /* otherwise leave top->left alone */

    if (rightTop != NULL) {
        SplayNodeSetLeftChild(rightFirst, SplayNodeRightChild(top));
        SplayNodeSetRightChild(top, rightTop);

        if (tree->updateNode != NULL) {
            /* Update client property using pointer reversal (Ugh!). */
            SplayNode node, parent, leftChild;

            /* Reverse the pointers between rightTop and rightFirst */
            /* ightFirst is not reversed. */
            node = rightTop;
            parent = NULL;
            while(node != rightFirst) {
                leftChild = SplayNodeLeftChild(node);
                SplayNodeSetLeftChild(node, parent); /* pointer reversal */
                parent = node;
                node = leftChild;
            }

            /* Now restore the pointers, updating the client property. */
            /* node is rightFirst, parent is the last parent (or NULL). */
            SplayNodeUpdate(tree, node);
            while(node != rightTop) {
                leftChild = node;
                node = parent;
                parent = SplayNodeLeftChild(node);
                SplayNodeSetLeftChild(node, leftChild); /* un-reverse pointer */
                SplayNodeUpdate(tree, node);
            }
        }
    }
    /* otherwise leave top->right alone */

    if (tree->updateNode != NULL)
        SplayNodeUpdate(tree, top);
}

static Bool BTFindResRange(Index *baseReturn, Index *limitReturn,
                           BT bt,
                           Index searchBase, Index searchLimit,
                           Count minLength, Count maxLength)
{
  Bool foundRes;         /* true if a reset bit is found */
  Index resBase;         /* base of a candidate reset range */
  Index unseenBase;      /* base of testing so far */
  Index minLimit;        /* limit of minimal acceptable range */
  Index resLimit;        /* limit of search for a candidate range */

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVERT(BT, bt);
  AVER(searchBase < searchLimit);
  AVER(minLength > 0);
  AVER(minLength <= maxLength);
  AVER(maxLength <= searchLimit - searchBase);

  foundRes = FALSE;     /* don't know first reset bit */
  minLimit = 0;         /* avoid spurious compiler warning */
  resBase = searchBase; /* haven't seen anything yet */
  unseenBase = searchBase;  /* haven't seen anything yet */
  resLimit = searchLimit - minLength + 1;

  while (resBase < resLimit) {
    Index setIndex;  /* index of last set bit found */
    Bool foundSet = FALSE; /* true if a set bit is found */

    /* Find the first reset bit if it's not already known */
    if (!foundRes) {
      BTFindRes(&foundRes, &resBase, bt, unseenBase, resLimit);
      if (!foundRes) {
        /* failure */
        return FALSE;
      }
      unseenBase = resBase + 1;
      minLimit = resBase + minLength;
    }

    /* Look to see if there is any set bit in the minimum range */
    BTFindSetHigh(&foundSet, &setIndex, bt, unseenBase, minLimit);
    if (!foundSet) {
      /* Found minimum range. Extend it. */
      Index setBase;   /* base of search for set bit */
      Index setLimit;  /* limit search for set bit */
      foundSet = FALSE;
      setBase = minLimit;
      setLimit = resBase + maxLength;
      if (setLimit > searchLimit)
        setLimit = searchLimit;
      if (setLimit > setBase)
        BTFindSet(&foundSet, &setIndex, bt, setBase, setLimit);
      if (!foundSet)
        setIndex = setLimit;
       
      AVER(setIndex - resBase >= minLength);
      AVER(setIndex - resBase <= maxLength);
      *baseReturn = resBase;
      *limitReturn = setIndex;
      return TRUE;
       
    } else {
      /* Range was too small. Try again */
      unseenBase = minLimit;
      resBase = setIndex + 1;
      if (resBase != minLimit) {
        /* Already found the start of next candidate range */
        minLimit = resBase + minLength;
        /* minLimit might just have gone out of bounds, but in that
         * case resBase >= resLimit and so the loop will exit. */
        AVER(minLimit <= searchLimit || resBase >= resLimit);
      } else {
        foundRes = FALSE;
      }
    }
  }

  /* failure */
  return FALSE;
}

static Res ArenaRootsWalk(Globals arenaGlobals, mps_roots_stepper_t f,
                          void *p, size_t s)
{
  Arena arena;
  rootsStepClosureStruct rscStruct;
  rootsStepClosure rsc = &rscStruct;
  Trace trace;
  ScanState ss;
  Rank rank;
  Res res;
  Seg seg;

  AVERT(Globals, arenaGlobals);
  AVER(FUNCHECK(f));
  /* p and s are arbitrary client-provided closure data. */
  arena = GlobalsArena(arenaGlobals);

  /* Scan all the roots with a minimal trace.  Invoke the scanner with a */
  /* rootsStepClosure, which is a subclass of ScanState and contains the */
  /* client-provided closure.  Supply a special fix method in order to */
  /* call the client closure.  This fix method must perform no tracing */
  /* operations of its own. */

  res = TraceCreate(&trace, arena, TraceStartWhyWALK);
  /* Have to fail if no trace available.  Unlikely due to .assume.parked. */
  if (res != ResOK)
    return res;

  /* ArenaRootsWalk only passes references to GCable pools to the client. */
  /* NOTE: I'm not sure why this is. RB 2012-07-24 */
  if (SegFirst(&seg, arena)) {
    do {
      if (PoolHasAttr(SegPool(seg), AttrGC)) {
        res = TraceAddWhite(trace, seg);
        AVER(res == ResOK);
      }
    } while (SegNext(&seg, arena, seg));
  }

  /* Make the roots grey so that they are scanned */
  res = RootsIterate(arenaGlobals, rootWalkGrey, trace);
  /* Make this trace look like any other trace. */
  arena->flippedTraces = TraceSetAdd(arena->flippedTraces, trace);

  rootsStepClosureInit(rsc, arenaGlobals, trace, RootsWalkFix, f, p, s);
  ss = rootsStepClosure2ScanState(rsc);

  for(rank = RankAMBIG; rank < RankLIMIT; ++rank) {
    ss->rank = rank;
    AVERT(ScanState, ss);
    res = RootsIterate(arenaGlobals, rootWalk, (void *)ss);
    if (res != ResOK)
      break;
  }

  /* Turn segments black again. */
  if (SegFirst(&seg, arena)) {
    do {
      if (PoolHasAttr(SegPool(seg), AttrGC)) {
        SegSetGrey(seg, TraceSetDel(SegGrey(seg), trace));
        SegSetWhite(seg, TraceSetDel(SegWhite(seg), trace));
      }
    } while (SegNext(&seg, arena, seg));
  }

  rootsStepClosureFinish(rsc);
  /* Make this trace look like any other finished trace. */
  trace->state = TraceFINISHED;
  TraceDestroy(trace);
  AVER(!ArenaEmergency(arena)); /* There was no allocation. */

  return res;
}

static void bufferNoReassignSeg(Buffer buffer, Seg seg)
{
  AVERT(Buffer, buffer);
  AVERT(Seg, seg);
  NOTREACHED; /* .noseg */
}

Size VMReserved(VM vm)
{
  AVERT(VM, vm);
  return vm->reserved;
}

DEFINE_CLASS(Inst, Inst, klass)
{
  InstClassInitInternal(klass);
  klass->instStruct.klass = CLASS(InstClass);
  AVERT(InstClass, klass);
}

Size VMMapped(VM vm)
{
  AVERT(VM, vm);
  return vm->mapped;
}

void FreelistFinish(Freelist fl)
{
  AVERT(Freelist, fl);
  fl->sig = SigInvalid;
  fl->list = NULL;
}

Res VMCreate(VM *vmReturn, Size size)
{
  void *addr;
  Align align;
  int zero_fd;
  VM vm;
  Res res;

  AVER(vmReturn != NULL);

  align = (Align)sysconf(_SC_PAGESIZE);
  AVER(SizeIsP2(align));
  size = SizeAlignUp(size, align);
  if((size == 0) || (size > (Size)(size_t)-1))
    return ResRESOURCE;

  zero_fd = open("/dev/zero", O_RDONLY);
  if(zero_fd == -1)
    return ResFAIL;

  /* Map in a page to store the descriptor on. */
  addr = mmap((void *)0, (size_t)SizeAlignUp(sizeof(VMStruct), align),
              PROT_READ | PROT_WRITE, MAP_PRIVATE,
              zero_fd, (off_t)0);
  if(addr == MAP_FAILED) {
    AVER(errno == ENOMEM || errno == EAGAIN); /* .assume.mmap.err */
    res = (errno == ENOMEM || errno == EAGAIN) ? ResMEMORY : ResFAIL;
    goto failVMMap;
  }
  vm = (VM)addr;

  vm->zero_fd = zero_fd;
  vm->align = align;

  /* .map.reserve: MAP_AUTORESRV is necessary to avoid reserving swap. */
  addr = mmap((void *)0, (size_t)size, PROT_NONE, MAP_SHARED | MAP_AUTORESRV,
	      zero_fd, (off_t)0);
  if(addr == MAP_FAILED) {
    AVER(errno == ENOMEM); /* .assume.mmap.err */
    res = (errno == ENOMEM) ? ResRESOURCE : ResFAIL;
    goto failReserve;
  }

  vm->base = (Addr)addr;
  vm->limit = AddrAdd(vm->base, size);
  vm->reserved = size;
  vm->mapped = (Size)0;

  vm->sig = VMSig;

  AVERT(VM, vm);

  EVENT_PAA(VMCreate, vm, vm->base, vm->limit);

  *vmReturn = vm;
  return ResOK;

failReserve:
  (void)munmap((void *)vm, (size_t)SizeAlignUp(sizeof(VMStruct), align));
failVMMap:
  (void)close(zero_fd);
  return res;
}

/* FreelistBlockNext -- return the next block in the list, or NULL if
 * there are no more blocks.
 */
static FreelistBlock FreelistBlockNext(FreelistBlock block)
{
  AVERT(FreelistBlock, block);
  return FreelistTagReset(block->small.next);
}