Introduction

.intro: This is the design of the Bit Tables module. A Bit Table is a linear array of bits. A Bit Table of length n is indexed using an integer from 0 up to (but not including) n. Each bit in a Bit Table can hold either the value 0 (FALSE) or 1 (TRUE). A variety of operations are provided including: get, set, and reset individual bits; set and reset a contiguous range of bits; search for a contiguous range of reset bits; making a "negative image" copy of a range.

.readership: MPS developers.

Definitions

.def.set: Set

Used as a verb meaning to assign the value 1 or TRUE to a bit. Used descriptively to denote a bit containing the value 1. Note 1 and TRUE are synonyms in MPS C code (see Bool).

.def.reset: Reset

Used as a verb meaning to assign the value 0 or FALSE to a bit. Used descriptively to denote a bit containing the value 0. Note 0 and FALSE are synonyms in MPS C code (see Bool).

.def.bt: Bit Table

A Bit Table is a mapping from [0, n) to {0,1} for some n, represented as a linear array of bits.

.def.bt.justify: They are called Bit Tables because a single bit is used to encode whether the image of a particular integer under the map is 0 or 1.

.def.range: Range

A contiguous sequence of bits in a Bit Table. Ranges are typically specified as a base--limit pair where the range includes the position specified by the base, but excludes that specified by the limit. The mathematical interval notation for half-open intervals, [base, limit), is used.

Requirements

.req.bit: The storage for a Bit Table of n bits shall take no more than a small constant addition to the storage required for n bits. .req.bit.why: This is so that clients can make some predictions about how much storage their algorithms use. A small constant is allowed over the minimal for two reasons: inevitable implementation overheads (such as only being able to allocate storage in multiples of 32 bits), extra storage for robustness or speed (such as signature and length fields).

.req.create: A means to create Bit Tables. .req.create.why: Obvious.

.req.destroy: A means to destroy Bit Tables. .req.destroy.why: Obvious.

.req.ops: The following operations shall be supported:

• .req.ops.get: Get. Get the value of a bit at a specified index.
• .req.ops.set: Set. Set a bit at a specified index.
• .req.ops.reset: Reset. Reset a bit at a specified index.

.req.ops.minimal.why: Get, Set, Reset, are the minimal operations. All possible mappings can be created and inspected using these operations.

• .req.ops.set.range: SetRange. Set a range of bits. .req.ops.set.range.why: It's expected that clients will often want to set a range of bits; providing this operation allows the implementation of the BT module to make the operation efficient.
• .req.ops.reset.range: ResetRange. Reset a range of bits. .req.ops.reset.range.why: as for SetRange, see .req.ops.set.range.why.
• .req.ops.test.range.set: IsSetRange. Test whether a range of bits are all set. .req.ops.test.range.set.why: Mostly for checking. For example, often clients will know that a range they are about to reset is currently all set, they can use this operation to assert that fact.
• .req.ops.test.range.reset: IsResetRange. Test whether a range of bits are all reset. .req.ops.test.range.reset.why As for IsSetRange, see .req.ops.test.range.set.why.
• .req.ops.find: Find a range, which we'll denote [i, j), of at least L reset bits that lies in a specified subrange of the entire Bit Table. Various find operations are required according to the (additional) properties of the required range:
  • .req.ops.find.short.low: FindShortResetRange. Of all candidate ranges, find the range with least j (find the leftmost range that has at least L reset bits and return just enough of that). .req.ops.find.short.low.why: Required by client and VM arenas to allocate segments. The arenas implement definite placement policies (such as lowest addressed segment first) so they need the lowest (or highest) range that will do. It's not currently useful to allocate segments larger than the requested size, so finding a short range is sufficient.
  • .req.ops.find.short.high: FindShortResetRangeHigh. Of all candidate ranges, find the range with greatest i (find the rightmost range that has at least L reset bits and return just enough of that). .req.ops.find.short.high.why: Required by arenas to implement a specific segment placement policy (highest addressed segment first).
  • .req.ops.find.long.low: FindLongResetRange. Of all candidate ranges, identify the ranges with least i and of those find the one with greatest j (find the leftmost range that has at least L reset bits and return all of it). .req.ops.find.long.low.why Required by the mark and sweep Pool Classes (AMS, AWL, LO) for allocating objects (filling a buffer). It's more efficient to fill a buffer with as much memory as is conveniently possible. There's no strong reason to find the lowest range but it's bound to have some beneficial (small) cache effect and makes the algorithm more predictable.
  • .req.ops.find.long.high: FindLongResetRangeHigh. Provided, but not required, see .non-req.ops.find.long.high.
• .req.ops.copy: Copy a range of bits from one Bit Table to another Bit Table. Various copy operations are required:
  • .req.ops.copy.simple: Copy a range of bits from one Bit Table to the same position in another Bit Table. .req.ops.copy.simple.why: Required to support copying of the tables for the "low" segment during segment merging and splitting, for pools using tables (for example, PoolClassAMS).
  • .req.ops.copy.offset: Copy a range of bits from one Bit Table to an offset position in another Bit Table. .req.ops.copy.offset.why: Required to support copying of the tables for the "high" segment during segment merging and splitting, for pools which support this (currently none, as of 2000-01-17).
  • .req.ops.copy.invert: Copy a range of bits from one Bit Table to the same position in another Bit Table inverting all the bits in the target copy. .req.ops.copy.invert.why: Required by colour manipulation code in PoolClassAMS and PoolClassLO.

.req.speed: Operations shall take no more than a few memory operations per bit manipulated. .req.speed.why: Any slower would be gratuitous.

.req.speed.fast: The following operations shall be very fast:

• .req.speed.fast.find.short: FindShortResRange (the operation used to meet .req.ops.find.short.low) FindShortResRangeHigh (the operation used to meet .req.ops.find.short.high).

  .req.speed.fast.find.short.why: These two are used by the client arena (design.mps.arena.client) and the VM arena (design.mps.arena.vm) for finding segments in page tables. The operation will be used sufficiently often that its speed will noticeably affect the overall speed of the MPS. They will be called with a length equal to the number of pages in a segment. Typical values of this length depend on the pool classes used and their configuration, but we can expect length to be small (1 to 16) usually. We can expect the Bit Table to be populated densely where it is populated at all, that is set bits will tend to be clustered together in subranges.

• .req.speed.fast.find.long: FindLongResRange (the operation used to meet .req.ops.find.long.low)

  .req.speed.fast.find.long.why: Used in the allocator for PoolClassAWL (design.mps.poolawl), PoolClassAMS (design.mps.poolams), PoolClassEPVM (design.mps.poolepvm(0)). Of these AWL and EPVM have speed requirements. For AWL the length of range to be found will be the length of a Dylan table in words. According to mail.tony.1999-05-05.11-36, only <entry-vector> objects are allocated in AWL (though not all <entry-vector> objects are allocated in AWL), and the mean length of an <entry-vector> object is 486 Words. No data for EPVM alas.

.req.speed.fast.other.why: We might expect mark and sweep pools to make use of Bit Tables, the MPS has general requirements to support efficient mark and sweep pools, so that imposes general speed requirements on Bit Tables.

Non requirements

The following are not requirements but the current design could support them with little modification or does support them. Often they used to be requirements, but are no longer, or were added speculatively or experimentally but aren't currently used.

• .non-req.ops.test.range.same: RangesSame. Test whether two ranges that occupy the same positions in different Bit Tables are the same. This used to be required by PoolClassAMS, but is no longer. Currently (1999-05-04) the functionality still exists.
• .non-req.ops.find.long.high: FindLongResetRangeHigh. (see .req.ops.find) Of all candidate ranges, identify the ranges with greatest j and of those find the one with least i (find the rightmost range that has at least L reset bits and return all of it). Provided for symmetry but only currently used by the BT tests and cbstest.c.

Background

.background: Originally Bit Tables were used and implemented by PoolClassLO (design.mps.poollo). It was decided to lift them out into a separate module when designing the Pool to manage Dylan Weak Tables which is also a mark and sweep pool and will make use of Bit Tables (see design.mps.poolawl).

.background.analysis: analysis.mps.bt(0) contains some of the analysis of the design decisions that were and were not made in this document.

Clients

.clients: Bit Tables are used throughout the MPS but the important uses are in the client and VM arenas (design.mps.arena.client(0) and design.mps.arena.vm) a bit table is used to record whether each page is free or not; several pool classes (PoolClassLO, PoolClassEPVM, PoolClassAMS) use bit tables to record which locations are free and also to store colour.

Overview

.over: Mostly, the design is as simple as possible. The significant complications are iteration (see .iteration below) and searching (see .fun.find-res-range below) because both of these are required to be fast.

Interface

typedef Word *BT

.if.representation.abstract: A Bit Table is represented by the type BT.

.if.declare: The module declares a type BT and a prototype for each of the functions below. The type is declared in impl.h.mpmtypes, the prototypes are declared in impl.h.mpm. Some of the functions are in fact implemented as macros in the usual way (doc.mps.ref-man.if-conv(0).macro.std).

.if.general.index: Many of the functions specified below take indexes. If otherwise unspecified an index must be in the interval [0, n) (note, up to, but not including, n) where n is the number of bits in the relevant Bit Table (as passed to the BTCreate() function).

.if.general.range: Where a range is specified by two indexes (base and limit), the index base, which specifies the beginning of the range, must be in the interval [0, n), and the index limit, which specifies the end of the range, must be in the interval [1, n] (note can be n), and base must be strictly less than limit (empty ranges are not allowed). Sometimes i and j are used instead of base and limit.

Res BTCreate(BT *btReturn, Arena arena, Count n)

.if.create: Attempts to create a table of length n in the arena control pool, putting the table in *btReturn. Returns ResOK if and only if the table is created OK. The initial values of the bits in the table are undefined (so the client should probably call BTResRange() on the entire range before using the BT). Meets .req.create.

void BTDestroy(BT t, Arena arena, Count n)

.if.destroy: Destroys the table t, which must have been created with BTCreate(). The value of argument n must be same as the value of the argument passed to BTCreate(). Meets .req.destroy.

size_t BTSize(Count n)

.if.size: BTSize(n) returns the number of bytes needed for a Bit Table of n bits. BTSize() is a macro, but (BTSize)(n) will assert if n exceeds COUNT_MAX - MPS_WORD_WIDTH + 1. This is used by clients that allocate storage for the BT themselves. Before BTCreate() and BTDestroy() were implemented that was the only way to allocate a Bit Table, but is now deprecated.

int BTGet(BT t, Index i)

.if.get: BTGet(t, i) returns the i-th bit of the table t (that is, the image of i under the mapping). Meets .req.ops.get.

void BTSet(BT t, Index i)

.if.set: BTSet(t, i) sets the i-th bit of the table t (to 1). BTGet(t, i) will now return 1. Meets .req.ops.set.

void BTRes(BT t, Index i)

.if.res: BTRes(t, i) resets the i-th bit of the table t (to 0). BTGet(t, i) will now return 0. Meets .req.ops.reset.

void BTSetRange(BT t, Index base, Index limit)

.if.set-range: BTSetRange(t, base, limit) sets the range of bits [base, limit) in the table t. BTGet(t, x) will now return 1 for base ≤ x < limit. Meets .req.ops.test.range.set.

void BTResRange(BT t, Index base, Index limit)

.if.res-range: BTResRange(t, base, limit) resets the range of bits [base, limit) in the table t. BTGet(t, x) will now return 0 for base ≤ x < limit. Meets .req.ops.test.range.reset.

Bool BTIsSetRange(BT bt, Index base, Index limit)

.if.test.range.set: Returns TRUE if all the bits in the range [base, limit) are set, FALSE otherwise. Meets .req.ops.test.range.set.

Bool BTIsResRange(BT bt, Index base, Index limit)

.if.test.range.reset: Returns TRUE if all the bits in the range [base, limit) are reset, FALSE otherwise. Meets .req.ops.test.range.reset.

Bool BTRangesSame(BT BTx, BT BTy, Index base, Index limit)

.if.test.range.same: returns TRUE if BTGet(BTx,i) equals BTGet(BTy,i) for i in [base, limit), and FALSE otherwise. Meets .non-req.ops.test.range.same.

.if.find.general: There are four functions (below) to find reset ranges. All the functions have the same prototype (for symmetry):

Bool find(Index *baseReturn, Index *limitReturn,
          BT bt,
          Index searchBase, Index searchLimit,
          Count length);

where bt is the Bit Table in which to search. searchBase and searchLimit specify a subset of the Bit Table to use, the functions will only find ranges that are subsets of [searchBase, searchLimit) (when set, *baseReturn will never be less than searchBase and *limitReturn will never be greater than searchLimit). searchBase and searchLimit specify a range that must conform to the general range requirements for a range [i, j), as per .if.general.range modified appropriately. length is the number of contiguous reset bits to find; it must not be bigger than searchLimit - searchBase (that would be silly). If a suitable range cannot be found the function returns FALSE (0) and leaves *baseReturn and *limitReturn untouched. If a suitable range is found then the function returns the range's base in *baseReturn and its limit in *limitReturn and returns TRUE (1).

Bool BTFindShortResRange(Index *baseReturn, Index *limitReturn, BT bt, Index searchBase, Index searchLimit, Count length)

.if.find-short-res-range: Finds a range of reset bits in the table, starting at searchBase and working upwards. This function is intended to meet .req.ops.find.short.low so it will find the leftmost range that will do, and never finds a range longer than the requested length (the intention is that it will not waste time looking).

Bool BTFindShortResRangeHigh(Index *baseReturn, Index *limitReturn, BT bt, Index searchBase, Index searchLimit, Count length)

.if.find-short-res-range-high: Finds a range of reset bits in the table, starting at searchLimit and working downwards. This function is intended to meet .req.ops.find.short.high so it will find the rightmost range that will do, and never finds a range longer than the requested length.

Bool BTFindLongResRange(Index *baseReturn, Index *limitReturn, BT bt, Index searchBase, Index searchLimit, Count length)

.if.find-long-res-range: Finds a range of reset bits in the table, starting at searchBase and working upwards. This function is intended to meet .req.ops.find.long.low so it will find the leftmost range that will do and returns all of that range (which can be longer than the requested length).

Bool BTFindLongResRangeHigh(Index *baseReturn, Index *limitReturn, BT bt, Index searchBase, Index searchLimit, Count length)

.if.find-long-res-range-high: Finds a range of reset bits in the table, starting at searchLimit and working downwards. This function is intended to meet .req.ops.find.long.high so it will find the rightmost range that will do and returns all that range (which can be longer than the requested length).

void BTCopyRange(BT fromBT, BT toBT, Index base, Index limit)

.if.copy-range: Overwrites the i-th bit of toBT with the i-th bit of fromBT, for all i in [base, limit). Meets .req.ops.copy.simple.

void BTCopyOffsetRange(BT fromBT, BT toBT, Index fromBase, Index fromLimit, Index toBase, Index toLimit)

.if.copy-offset-range: Overwrites the i-th bit of toBT with the j-th bit of fromBT, for all i in [toBase, toLimit) and corresponding j in [fromBase, fromLimit). Each of these ranges must be the same size. This might be significantly less efficient than BTCopyRange(). Meets .req.ops.copy.offset.

void BTCopyInvertRange(BT fromBT, BT toBT, Index base, Index limit)

.if.copy-invert-range: Overwrites the i-th bit of toBT with the inverse of the i-th bit of fromBT, for all i in [base, limit). Meets .req.ops.copy.invert.

Detailed design

unsigned long f(unsigned long i) {
    return i/32 + i%32;
}

unsigned long g(unsigned long i) {
   return (i>>5) + (i&31);
}

Testing

.test: The following tests are available or have been used during development.

.test.btcv: btcv.c. This is supposed to be a coverage test, intended to execute all of the module's code in at least some minimal way.

.test.landtest: landtest.c. This is a test of the Land module (design.mps.land) and its concrete implementations. It compares the functional operation of a Land with that of a BT so is a good functional test of either module.

.test.mmqa.120: MMQA_test_function!210.c. This is used because it has a fair amount of segment allocation and freeing so exercises the arena code that uses Bit Tables.

.test.bttest: bttest.c. This is an interactive test that can be used to exercise some of the BT functionality by hand.

.test.dylan: It is possible to modify Dylan so that it uses Bit Tables more extensively. See change.mps.epcore.brisling.160181 TEST1 and TEST2.

References

Document History

• 1997-03-04 David Jones. Initial drafts.
• 1999-04-29 David Jones. Prepared for review. Added full requirements section. Made notation more consistent throughout. Documented all functions.
• 2002-06-07 RB Converted from MMInfo database design document.
• 2013-03-12 GDR Converted to reStructuredText.

Copyright and License

Copyright © 2013–2020 Ravenbrook Limited.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.