store.c

Bug Summary

File:	subcmd/unitools/store.c
Warning:	line 705, column 23 Dereference of null pointer
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name store.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/kfp/aldor/aldor/aldor/subcmd/unitools -fcoverage-compilation-dir=/home/kfp/aldor/aldor/aldor/subcmd/unitools -resource-dir /usr/local/lib/clang/18 -D PACKAGE_NAME="aldor" -D PACKAGE_TARNAME="aldor" -D PACKAGE_VERSION="1.4.0" -D PACKAGE_STRING="aldor 1.4.0" -D PACKAGE_BUGREPORT="aldor@xinutec.org" -D PACKAGE_URL="" -D PACKAGE="aldor" -D VERSION="1.4.0" -D YYTEXT_POINTER=1 -D HAVE_STDIO_H=1 -D HAVE_STDLIB_H=1 -D HAVE_STRING_H=1 -D HAVE_INTTYPES_H=1 -D HAVE_STDINT_H=1 -D HAVE_STRINGS_H=1 -D HAVE_SYS_STAT_H=1 -D HAVE_SYS_TYPES_H=1 -D HAVE_UNISTD_H=1 -D STDC_HEADERS=1 -D HAVE_LIBREADLINE=1 -D HAVE_READLINE_READLINE_H=1 -D HAVE_READLINE_HISTORY=1 -D HAVE_READLINE_HISTORY_H=1 -D USE_GLOOP_SHELL=1 -D GENERATOR_COROUTINES=0 -D HAVE_DLFCN_H=1 -D LT_OBJDIR=".libs/" -I . -I ./../../src -I ../../src -internal-isystem /usr/local/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2026-01-15-223856-845667-1 -x c store.c
1/*****************************************************************************
*
* store.c: Storage management.
*
* Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
*
****************************************************************************/

9/*
*   Select one of:
*	STO_USE_BTREE	B-Tree based quick fit.
*	STO_USE_ONCE	Don't look back.
*	STO_USE_MALLOC	Based on malloc/free.
*
*
*   For STO_USE_BTREE, select
*   any of:
*	STO_TALLY	Keep storage use statistics.
*	STO_LONGJMP	Error handler can return when StoErr_CantBuild occurs.
*	STO_WATCH	Trace allocations and deallocations.
*	STO_CERTIFY	Trace tests controlling if statements, etc.
*      USE_MEMORY_CLIMATE  To over-ride the setting of stoAlloc codes.
*   one of:
*	STO_NEW_JUNK	Newly allocated store contains any old junk.
*	STO_NEW_AAAA	Newly allocated store contains 0xAAAAAA...
*	STO_NEW_ZERO	Newly allocated store contains zeros.
*   and one of:
*	STO_FREE_JUNK	Free storage contains any old junk.
*	STO_FREE_DDDD	Free storage contains 0xDDDDDD...
*
* For debugging support define STO_DEBUG_DISPLAY. This will cause the
* garbage collector to check for the GC_DETAIL and GC_CLASSIFY environment
* variables when the first GC takes place.
*
* The value of GC_DETAIL is used to control the output of stoShow(). The
* existence of GC_CLASSIFY determines whether or not tables showing the
* classification of pointers are displayed.
*
* By default blacklisting is not enabled since the current implementation
* doesn't have much effect (for good or ill). Define STO_CAN_BLACKLIST to
* enable it and then set the GC_BLACKLIST environment variable to actually
* use it at runtime.
*
* To speed up the computation of indices of quanta, fixed-size sections
* whose size is not an integral power of two we use division via a lookup
* table. Enable this by defining STO_DIVISION_BY_LOOKUP and suffer a
* penalty of a 48K table in static data.
*/

50#include "debug.h"
51#include "opsys.h"
52#include "store.h"
53#include "timer.h"

55/*
* If no other allocator is specified, used the B-Tree based by default.
*/
58#if !defined(STO_USE_BTREE)&& !defined(STO_USE_ONCE)&& !defined(STO_USE_MALLOC) && !defined(STO_USE_BOEHM)
59#  if __APPLE__
60#   define STO_USE_ONCE 1
61#  elif 0 && !defined(FOAM_RTS)
62#    define STO_USE_MALLOC
63#  else
64#    define STO_USE_BTREE
65#  endif
66#endif

68#include "axlgen0.h"
69#include "btree.h"
70#include "memclim.h"
71#include "util.h"

73/* this will create a debug version of GC that should be safer */
74#undef NDEBUG

76/*
* User programs can make limited checks on pointers to ensure
* that they do not attempt to write to areas of memory that
* are writable. Although we could give the user a much more
* precise result (such as this object is a free object on the
* heap) we choose not to.
*/
83#define POINTER_IS_INVALID(-1)		(-1)
84#define POINTER_IS_UNKNOWN( 0)		( 0)
85#define POINTER_IS_VALID( 1)		( 1)


88/*===========================================================================*/

90#ifdef STO_USE_BTREE

92#if defined(OS_WIN32)
93#include <windows.h>
94#endif


97/*
* B-Tree based allocator.
*
*
* At the coarsest level, memory has "page" granularity.
* Memory is used in contiguous sequences of pages, called "sections".
*
* The pages of this memory manager need not bear any relation to those
* of the operating system.  If the definitions coincide, however, then
* virtual memory performace should be better.
*
* Some pages contain pieces which must all be the same size.  These pieces
* are called "fixed" pieces.  Other pages do not dictate the size of the
* pieces they contain.	 These pieces are called "mixed".  There are also
* other types of pages for foreign inclusions and structures used by the
* allocator.  A page map keeps track of how each page is used.
*
* A section of one or more pages is layed out as follows:
* +-----------------------+--- - - - - - - - ---+-----------------------+
* | first page		   |			 | last page		 |
* +----++++ - ++++-----+--+--+ - - - - - - - +--+--+--+--+ - - +--+--+--+
* |head| info	  | gap | data						 |
* +----++++ - ++++-----+--+--+ - - - - - - - +--+--+--+--+ - - +--+--+--+
* Note that the data quanta are aligned at the last page boundary.
*
* Keeping info separate from data requires less space but more time.
* Space is saved since no padding is needed to align the data pointer.
* Finding the info for a piece takes more time, though.
*
* Compared to having a single tag table, keeping a tag table per section
* requires more memory access for tag lookup.	But a single tag table must be
* relocated when memory grows and will be much larger if pages are sparse.
*
* The fixed pieces which are not in use are kept in free lists, one for each
* fixed size.
*
* The handling of free mixed pieces is somewhat more complicated.
* The complications are introduced by the competing criteria that requests
* be satisfied quickly, and that storage be used as efficiently as possible.
*
* To use storage efficiently, fragmentaition must be avoided.	Three steps
* toward achieving this goal are
* (1) when a mixed piece is freed, it is merged with any adjacent mixed free
*     pieces to form a larger piece,
* (2) requests are satisfied using a "best fit" strategy, and
* (3) among best fits, the one with the lowest address is used.
*
* List-based implementations of best fit are slow so to achieve the speed
* objective, the free pieces are sorted by size in a B-tree.
* The keys into the B-tree are the sizes and the entries are doubly linked
* lists of same-size pieces.
*
* Using doubly linked lists means that the tree need be modified only when
* a new size is introduced or removed.	 This benefit is enhanced by rounding
* all mixed pieces up to a multiple of some size.
*/

154/*
* To do:
* -- When freeing the last piece in a section, return sect to free page list.
* -- Robustify btreeX functions to check for 0 return from newX.
* -- Audits for BTree node and DLL node pages
* -- Sort DLLs by address
* -- Think about using SLLs instead of DLLs
* -- Use osFree when possible
* -- Ask for only as many pages as needed at once.
* -- Modify mixedFrontier to be truly busy.
* -- If adjacent mixed pieces are gc-ed, merge before adding to BTree.
* -- Merge returned free pieces to mixed frontier, if possible.
* -- Increase qmSize for sections with larger pieces.
* -- Encode run lengths in PgInfo to speed up sectFor.
* -- Relocation based on pointer certainty.
* -- Remove setjmps for stoAllocInner_ErrorCatch by ensuring enough to start.
*/

172/*****************************************************************************
*
* :: Parameters
*
*****************************************************************************/

178#define LgPgSize12	  12	/* Log[2](PgSize). pagesTest ok for 3..15. */

180#define PgSize(1L<<12) (1L<<LgPgSize12)	/* Granularity for OS request. */

182#define PgGroup16		  16	/* Get this many pages at once from OS. */

184#define FixedSizePgGroup1   1	/* This many pages at once for fxmem. */

186#define FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))	   (sizeof(fixedSize)/sizeof(fixedSize[0]))
		/* Number of different fixed small sizes. */

189#define FixedSizeMax(32*sizeof(Pointer))	   (32*sizeof(Pointer))
		/* Maximum fixed small size. */

192#define STO_DIVISION_BY_LOOKUP1	1 
193#define STO_SECT_AND_PAGE_OF1	1 

195static Length fixedSize[] = {
1  * sizeof(Pointer),
2  * sizeof(Pointer),
3  * sizeof(Pointer),
4  * sizeof(Pointer),
6  * sizeof(Pointer),
8  * sizeof(Pointer),
10 * sizeof(Pointer),
12 * sizeof(Pointer),
16 * sizeof(Pointer),
20 * sizeof(Pointer),
24 * sizeof(Pointer),
FixedSizeMax(32*sizeof(Pointer))
208};				/* Fixed sizes for small allocations. */

210static int fixedSizeLog[] = {
0, 1, -1, 2, -2, 3, -3, -4, 4, -5, -6, 5 
     /*-1,-1,-1, -1,-1, -1, -1,-1, -1, -1, -1*/
213};


216#ifdef FOAM_RTS
217/*
* Ensure that these names agree with the CensusType enumeration in
* foam_c.h otherwise the results of stoTakeCensus will be meaningless.
*/
221static char *censusName[] = {
"Unknown",
"Bogus",
"BInt",
"DFlo",
"Closure",
"Record",
"RawRecord",
"DynFormat",
"Char[]",
"Bool[]",
"Byte[]",
"HInt[]",
"SInt[]",
"SFlo[]",
"DFlo[]",
"Word[]",
"Ptr[]",
"Trailing[]",
"EnvInfo",
"EnvLevel",
"Fluid",
"GlobalInfo",
"SaveState",
"Total",
246};
247#else
248/*
* Ensure that these names agree with the OB_* definitions in axlgen.h
* and axlobs.h otherwise the results of stoTakeCensus will be meaningless.
*/
252static char *censusName[] = {
"Unknown",
"Bogus",
"BInt",
"BTree",
"Bitv",
"Buffer",
"List",
"String",
"Symbol",
"Table",
"DNF",
"CCode",
"SExpr",
"CoMsg",
"SrcLine",
"Token",
"Doc",
"AbSyn",
"AbBind",
"Stab",
"Syme",
"TForm",
"TPoss",
"TConst",
"TQual",
"Foam",
"Lib",
"Archive",
"Total",
282};
283#endif


286/* We can't access the CensusType enumeration so we guess the limit */
287#define	STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0]))	(sizeof(censusName)/sizeof(censusName[0]))
288static ULong	censusBefore[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0]))];
289static ULong	censusAfter[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0]))];
290static ULong	censusMemBefore[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0]))];
291static ULong	censusMemAfter[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0]))];


294#ifdef STO_DIVISION_BY_LOOKUP1
295static short stoDivTable[6][PgSize(1L<<12)];
296#endif


299static UShort fixedSizeFor     [FixedSizeMax(32*sizeof(Pointer))+1];
		/* Look up size to use. */
301static UByte  fixedSizeIndexFor[FixedSizeMax(32*sizeof(Pointer))+1];
		/* Index into size table. */

304#define MixedBTreeT16	 16	/* Min #branches for btree interior node. */
305#define MixedSizePgGroup2  2	/* At least this many pgs at once for mxmem. */
306#define MixedSizeQuantum(32*sizeof(Pointer)) FixedSizeMax(32*sizeof(Pointer))
		/* All mixed sizes are a multiple of this. */

309/*   - flo-po banished coz we don't want to risk exceptions in the runtime*/
310/* double GcEffectiveFactor = 0.3;    Get more pages unless this fraction free. */
311long GcEffectiveFactorNum=3;
312long GcEffectiveFactorDen=10;
313/* double GcGrowthFactor    = 1.4;    Grow the heap by this much if a Gc fails.*/
314long GcGrowthFactorNum=14;
315long GcGrowthFactorDen=10;
316long   GcMinGrowth       = (512*1024)/PgSize(1L<<12); /* Grow by a minumum of 0.5meg */

318long GcFrugalFactorNum = 70;
319long GcFrugalFactorDen = 100;


322/* Set GC_FRUGAL to enable more reticent heap growth */
323static Bool GcIsFrugal = false((int) 0);


326/* Object information.
* Maybe consider using bitmap for these... 
* Note that in reality we only have 32 objects (28 of which are taken
* by the compiler for internal data structures).
*/
331#define OB_MAX256 256

333/*****************************************************************************/
334/***          These MUST be the same as their cousins in foam_c.h          ***/
335/*****************************************************************************/
336typedef Pointer (*StoFiFun)();

338typedef struct _StoFiProg
339{
StoFiFun fun;
StoFiFun fcall;
Pointer  progInfo;
Pointer  data;
344} *StoFiProg;

346typedef struct _StoFiClos
347{
Pointer env;
StoFiProg prog;
350} *StoFiClos;

352#define stoFiCFun(t, fn)(*((t (*)())(fn)->prog->fun))	(*((t (*)())(fn)->prog->fun))
353#define stoFiCCall2(t,fn,a,b)((*((t (*)())(fn)->prog->fun))((fn)->env,a,b))	(stoFiCFun(t,fn)(*((t (*)())(fn)->prog->fun))((fn)->env,a,b))
354/*****************************************************************************/

356static char stoObRegistered[OB_MAX256];
357static char stoObNoInternalPtrs[OB_MAX256];
358static StoFiClos stoObAldorTracer[OB_MAX256];
359static StoTraceFun stoObCTracer[OB_MAX256];

361/*****************************************************************************
*
* :: Controls
*
*****************************************************************************/

367static Bool	gcLevel		= StoCtl_GcLevel_Automatic2;
368static FILE	*gcTraceFile	= 0;
369static Bool	stoMustWash	= true1;
370static Bool	stoMustTag      = true1;

372static Bool     markingStats    = false((int) 0);

374#ifdef STO_DEBUG_DISPLAY
375# define stoDebug((int) 0)		true1
376#else
377# define stoDebug((int) 0)		false((int) 0)
378#endif

380/*****************************************************************************
*
* :: Benchmarks
*
*****************************************************************************/

386static struct tmTimer gcTimer;

388/*****************************************************************************
*
* :: Types
*
*****************************************************************************/

394enum PgKind {
PgFree,		/* Page is available. */
PgBusyFirst,	/* First of related busy pages. */
PgBusyFollow,	/* Subsequent related busy pages. */
PgPgMap,	/* Page used by pgMap. */
PgBTree,	/* Page used by free tree as node. */
PgDLL,		/* Page used by free tree carrier. */
PgForeign	/* Page is not ours. */
402};

404typedef char		Page[PgSize(1L<<12)];	/* Type for striding across pages. */
405typedef UByte		PgInfo;		/* Type for compact page map info. */
406typedef UByte		QmInfo;		/* Type for compact quantum info. */

408typedef enum   PgKind	PgKind;		/* Page is available, busy, etc. */

410typedef struct Section	Section;	/* A section of busy pages. */
411typedef struct FxMem	FxMem;		/* Ptr to fixed pcs of a given size. */
412typedef struct MxMem	MxMem;		/* Ptr to mixed pcs of a given size. */


415/*****************************************************************************
*
* :: Forward Declarations
*
*****************************************************************************/

421localstatic  MostAlignedType *stoDefaultError	 (int errnum);
422static StoErrorFun	stoError	 = stoDefaultError;

424localstatic Bool stoNeedsMoreHeadroom(int);
425localstatic Length sectQmCount(Length, Length);

427extern void stoTakeCensus(AInt);

429/*****************************************************************************
*
* :: Conditional Code
*
*****************************************************************************/

435/*
* Set debugging configuration, if appropriate.
*/
438#ifndef NDEBUG
439#  define STO_TALLY

441#  if !defined(STO_NEW_JUNK) && !defined(STO_NEW_ZERO)
442#    define STO_NEW_AAAA
443#  endif

445#  if !defined(STO_FREE_JUNK)
446#    define STO_FREE_DDDD
447#  endif
448#endif


451/*
* Conditional code to fill and test memory.
*/
454#if defined(STO_NEW_ZERO)
455#  define STO_NEW_CHAR0xAA	0x00
456#endif
457#if defined(STO_NEW_AAAA)
458#  define STO_NEW_CHAR0xAA	0xAA
459#endif
460#if defined(STO_FREE_DDDD)
461#  define STO_FREE_CHAR0xDD 0xDD
462#endif

464#if defined(STO_NEW_CHAR0xAA)
465# define newFill(s,n)(stoMustWash ? memlset (s,0xAA,n) : 0)		(stoMustWash ? memlset (s,STO_NEW_CHAR0xAA,n) : 0)
466#else
467# define newFill(s,n)(stoMustWash ? memlset (s,0xAA,n) : 0)		Nothing
468#endif

470#if defined(STO_FREE_CHAR0xDD)
471# define freeFill(s,n)(stoMustWash ? memlset (s,0xDD,n) : 0)		(stoMustWash ? memlset (s,STO_FREE_CHAR0xDD,n) : 0)
472# define freeAssert(s,n)(stoMustWash ? memltest(s,0xDD,n) : 0)	(stoMustWash ? memltest(s,STO_FREE_CHAR0xDD,n) : 0)
473#else
474# define freeFill(s,n)(stoMustWash ? memlset (s,0xDD,n) : 0)		Nothing
475# define freeAssert(s,n)(stoMustWash ? memltest(s,0xDD,n) : 0)	Nothing
476#endif


479/*
* Conditional code to keep track of storage.
*/
482#define STO_TALLY
483#ifdef STO_TALLY
484# define stoTally(expr)(expr)		(expr)
485#else
486# define stoTally(expr)(expr)		Nothing
487#endif


490/*
* Conditional code to control tracing.
*/


495#ifdef STO_WATCH
496#  define stoWatch(s,p,n,f)	stoWatchReally(s,p,n,f)
497#else
498#  define stoWatch(s,p,n,f)	Nothing
499#endif

501#ifdef STO_CERTIFY
502#  define stoCertify(n,c)(c)	stoCertifyReally((n), (c) ? true1 : false((int) 0))
503#else
504#  define stoCertify(n,c)(c)	(c)
505#endif

507#define IF(c)if ((c))			if    (stoCertify(__LINE__,c)(c))
508#define WHILE(c)while ((c))		while (stoCertify(__LINE__,c)(c))

510/*****************************************************************************
*
* :: Storage manager state
*
*****************************************************************************/

516static int	stoIsInit  = 0; /* Is the storage manager initialized? */

518static char	*heapStart,	/* Start of allocator area. */
*heapEnd;	/* Past end of allocator area. */

521static PgInfo	*pgMap;		/* Info for each page we care about. */
522static Length	pgMapSize;	/* Number of pages we care about. */
523static Length	pgMapUses;	/* Space occupied by page map. */

525static FxMem	*fixedPieces[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
526static BTree	mixedPieces;
527static MxMem	*mixedFrontier;

529ULong	       stoBytesOwn;	 /* Total owned by allocator. */
530ULong	       stoBytesAlloc;	 /* Total ever allocated. */
531ULong	       stoBytesFree;	 /* Total ever freed. */
532ULong	       stoBytesGc;	 /* Total ever garbage collected. */
533ULong	       stoBytesBlack;	 /* Total blacklisted */
534ULong	       stoPiecesGc[STO_CODE_LIMIT32];	/* # this time, by code. */


537/*
* freeFixedPieces[i] is the number of free pieces in fixedPieces[i]
* busyFixedPieces[i] is the number of busy pieces of that size.
* freeMixedBytes is the number of bytes held in mixed-sized free-tree.
* busyMixedBytes is the number of bytes held in mixed-size busy pieces.
*/
543static ULong	freeFixedPieces[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
544static ULong	busyFixedPieces[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
545static ULong	freeMixedBytes, busyMixedBytes;

547/****************************************************************************
*
* :: Debugging
*
***************************************************************************/

553#define stoWatchAlloc(p,n)	stoWatch("Alloc   ",(p), (n), true)
554#define stoWatchFree(p)		stoWatch("Free    ",(p), 0,   true)
555#define stoWatchFrontier(p)	Nothing
556#define stoWatchMarkFrom(p)	stoWatch("Mark fr ",(p), 0,   false)
557#define stoWatchMarkTo(p)       stoWatch("Mark to ",(p), 0,   false)


560static int stoWatchCount = 0;

562int
563stoWatchReally(String title, Pointer p, ULong n, Bool audit)
564{
const char *fmt = n ? "[[%4d %s: %p (%lu)]]\n" : "[[%4d %s: %p]]\n";

fprintf(osStderr, fmt, stoWatchCount, title, p, n);
fflush (osStderr);

if (audit) {
stoAudit();
}

stoWatchCount++;
return 0;
576}

578Bool
579stoCertifyReally(int loc, Bool flag)
580{
fprintf(osStderr, " %d-%s", loc, flag ? "T" : "F");
return flag;
583}

585TmTimer
586stoGcTimer(void)
587{
return &gcTimer;
589}

591/****************************************************************************
*
* :: Basic allocation
*
***************************************************************************/

597/*
* Obtain an aligned area from the operating system.
*/
600localstatic Pointer
601byteGetIfCan(Length alignment, ULong nbytes, ULong *pnbytesGot)
602{
Pointer p;

osAllocAlignHint(alignment);

nbytes += alignment;
p	= osAlloc(&nbytes);

if (p != 0) {
freeFill(p, nbytes)(stoMustWash ? memlset (p,0xDD,nbytes) : 0);
stoBytesOwn += nbytes;
}

/*
* Round up appropriately.
*/
if (p != 0) {
long	plong, rem;

plong  = ptrToLong(p)((long) (p));
rem    = plong % alignment;
plong += (rem == 0) ? 0 : alignment - rem;
nbytes-= rem;

p = ptrFrLong(plong)((Pointer)(plong));
}

if (pnbytesGot) *pnbytesGot = nbytes;

return p;
632}



636/*****************************************************************************
*
* :: Page map
*
* Modifies globals: pgMap, pgMapSize, pgMapUses
* Uses globals:     heapStart, heapEnd
*
****************************************************************************/

645# define PgMask~((1L<<12)-1)		~(PgSize(1L<<12)-1)
646#ifdef STO_SECT_AND_PAGE_OF1
647# define pgOf(p)(((Pointer)((char *)(heapStart) + ((((long)((char *)(p) - (char
 *)(heapStart))) & ~((1L<<12)-1))))))	(ptrOff(heapStart, (ptrDiff(p, heapStart) & PgMask))((Pointer)((char *)(heapStart) + ((((long)((char *)(p) - (char
 *)(heapStart))) & ~((1L<<12)-1))))))
648#endif
649# define pgAt(n)((Page *)((Pointer)((char *)(heapStart) + ((n) * (1L<<12
)))))	((Page *)ptrOff(heapStart, (n) * PgSize)((Pointer)((char *)(heapStart) + ((n) * (1L<<12)))))
650# define pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12)	(ptrDiff((char *)(p), heapStart)((long)((char *)((char *)(p)) - (char *)(heapStart))) >> LgPgSize12)
651# define pgLen(nb)((Length) (((nb) + (1L<<12) - 1) >> 12))	((Length) (((nb) + PgSize(1L<<12) - 1) >> LgPgSize12))
652# define isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd))))	(ptrLE(heapStart,(p))(((Pointer)(heapStart)) <= ((Pointer)((p)))) && ptrLT((p),heapEnd)(((Pointer)((p))) < ((Pointer)(heapEnd))))


655localstatic Page *	pagesFind(Length npages);
656localstatic void	pagesPut (Page *, Length npages);

658/*
* Obtain and free storage for page map.
*/
661localstatic PgInfo *
662pgmapAlloc(Length npgMapUses)
663{
PgInfo	*npgMap = 0;
if (pgMap)
npgMap = (PgInfo *) pagesFind(npgMapUses);
if (!npgMap)
npgMap = (PgInfo *) byteGetIfCan(PgSize(1L<<12),PgSize(1L<<12)*npgMapUses,NULL((void*)0));
return npgMap;
670}

672localstatic void
673pgmapFree(PgInfo *opgMap, Length opgMapUses)
674{
char	*b, *e;
b = (char *) opgMap;
e = b + PgSize(1L<<12) * opgMapUses - 1;

if (isInHeap(b)((((Pointer)(heapStart)) <= ((Pointer)((b)))) && (
((Pointer)((b))) < ((Pointer)(heapEnd)))) && isInHeap(e)((((Pointer)(heapStart)) <= ((Pointer)((e)))) && (
((Pointer)((e))) < ((Pointer)(heapEnd)))))
pagesPut((Page *) opgMap, opgMapUses);
681}

683/*
* Create the initial page map.
*/
686localstatic void
687pgmapInit(void)
688{
pgMap = 0;

pgMap = pgmapAlloc(1);
if (!pgMap) return;

pgMapUses = 1;
pgMapSize = 1;
696}

698/*
* Update the page map for count pages starting at p.
*/
701localstatic void
702pgmapMod(Page *p, Length count, PgKind kind)
703{
PgInfo	*m = pgMap + pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12);
while (count--) *m++ = kind;
36
←
Loop condition is true.  Entering loop body→
37
←
Null pointer value stored to 'm'→
38
←
Dereference of null pointer
706}

708/*
* Search for the first free page sequence long enough. Failure is -1.
*/
711int pgmapFoundFreeLastTime=0 ;

713localstatic int
714pgmapFindFree(Length count)
715{
int	i, i0, iL;

/* look after previous find */
for (i = pgmapFoundFreeLastTime ; i < pgMapSize; i++)
if (pgMap[i] == PgFree) {
	i0 = i;
	iL = i + count;
	if (iL > pgMapSize) return -1;
	for ( ; i < iL; i++) {
		if (pgMap[i] != PgFree) break;
		}
	if (i == iL) {
		pgmapFoundFreeLastTime = i0;
		return i0;
		}
}
/* now look at the bits we missed */
for (i = 0 ; i < pgmapFoundFreeLastTime ; i++)
if (pgMap[i] == PgFree) {
	i0 = i;
	iL = i + count;
	if (iL > pgMapSize) return -1;
	for ( ; i < iL; i++) {
		if (pgMap[i] != PgFree) break;
		}
	if (i == iL) {
		pgmapFoundFreeLastTime = i0;
		return i0;
		}
}
pgmapFoundFreeLastTime =0 ;
return -1;
748}

750/*
* Count the number of free pages.
*/
753localstatic int
754pgmapCountFree(void)
755{
int	i, nfree;

nfree = 0;
for (i = 0; i < pgMapSize; i++) if (pgMap[i] == PgFree) nfree++;
return nfree;
761}

763/*
* Count the number of non-foreign pages.
*/
766localstatic int
767pgmapCountDomestic(void)
768{
int	i, ndom;

ndom = 0;
for (i = 0; i < pgMapSize; i++) if (pgMap[i] != PgForeign) ndom++;
return ndom;
774}

776/*
* Guarantee page map is large enough.
*/
779localstatic int
780pgmapNeed(Length count)
781{
PgInfo	 *opgMap    = pgMap,	 *npgMap;
Length	 opgMapUses = pgMapUses, npgMapUses = pgLen(count)((Length) (((count) + (1L<<12) - 1) >> 12));

if (opgMapUses >= npgMapUses) return 1;

npgMap = pgmapAlloc(npgMapUses);
if (!npgMap) return 0;

memcpy(npgMap, opgMap, pgMapSize * sizeof(PgInfo));

pgMap	  = (PgInfo*) npgMap;
pgMapUses = npgMapUses;

pgmapFree(opgMap, opgMapUses);

return 1;
798}

800/*
* Slide page map to insert extra pages at beginning.
*/
803localstatic int
804pgmapSlide(Length count, PgKind kind)
805{
PgInfo	*oend, *nend;
Length	i;

if (count == 0) return 1;

if (!pgmapNeed(pgMapSize + count)) return 0;

oend = pgMap + pgMapSize;
nend = oend  + count;

for (i = 0; i < pgMapSize; i++) *--nend = *--oend;
for (i = 0; i < count;	   i++) *--nend = kind;

pgMapSize += count;

return 1;
822}

824/*
* Extend page map with extra pages at the end.
*/
827localstatic int
828pgmapExtend(Length count, PgKind kind)
829{
PgInfo	*oend;
Length	i;

if (!pgmapNeed(pgMapSize + count)) return 0;

oend = pgMap + pgMapSize;

for (i = 0; i < count; i++) *oend++ = kind;

pgMapSize += count;

return 1;
842}


845/*****************************************************************************
*
* :: Heap page management
*
* Modifies globals: heapStart, heapEnd
*
****************************************************************************/

853/*
* Add a stretch of free pages.
* The page map and heap limits are updated accordingly.
* A return value of 1 indicates success; 0 indicates failure.
*
* The page map may or may not include info about its own pages.
* If it does, then they may be noted as PgForeign or PgPgMap.
*/
861localstatic int
862pagesAdd(Length nBest, Length nMin)
863{
ULong	nbytesGot, nRequest, nForeign;
char	*b, *e;
int	ok;

/* Request ideal ammount; back off until minimum. */
nRequest  = (nBest > PgGroup16) ? nBest : PgGroup16;
for (;;) {
b = (char *) byteGetIfCan(PgSize(1L<<12), nRequest*PgSize(1L<<12), &nbytesGot);
if (nbytesGot % PgSize(1L<<12) != 0) nbytesGot -= nbytesGot % PgSize(1L<<12);

e = (char *) ptrOff(b,nbytesGot)((Pointer)((char *)(b) + (nbytesGot)));
if (b) break;
if (nRequest <= nMin) return 0;
nRequest = (nRequest >= 2*nMin) ? nRequest / 2 : nRequest - 1;
}

nRequest = nbytesGot >> LgPgSize12;
nForeign = ptrGE(b, heapEnd)(((Pointer)(b)) >= ((Pointer)(heapEnd)))   ? pgLen(ptrDiff(b, heapEnd))((Length) (((((long)((char *)(b) - (char *)(heapEnd)))) + (1L
<<12) - 1) >> 12))
 : ptrLE(e, heapStart)(((Pointer)(e)) <= ((Pointer)(heapStart))) ? pgLen(ptrDiff(heapStart, e))((Length) (((((long)((char *)(heapStart) - (char *)(e)))) + (
1L<<12) - 1) >> 12))
 : 0 ;

/* Update page map. */
if (ptrGE(b, heapEnd)(((Pointer)(b)) >= ((Pointer)(heapEnd)))) {
/* New store is above. */
heapEnd = e;
ok = pgmapExtend(nRequest + nForeign, PgForeign);
if (!ok) return 0;
}
else if (ptrLE(e, heapStart)(((Pointer)(e)) <= ((Pointer)(heapStart)))) {
/* New store is below. */
heapStart = b;
ok = pgmapSlide(nRequest + nForeign,  PgForeign);
if (!ok) return 0;
}
else {
/* New store is in middle (formerly foreign). */
}

/* Add pages to heap. */
pagesPut((Page *) b, nRequest);

/* If heap now includes page map, indicate it. */
b = (char *) pgMap;
e = (char *) ptrOff(b, pgMapUses * PgSize)((Pointer)((char *)(b) + (pgMapUses * (1L<<12))));
if (isInHeap(b)((((Pointer)(heapStart)) <= ((Pointer)((b)))) && (
((Pointer)((b))) < ((Pointer)(heapEnd)))) && isInHeap(ptrOff(e,-1))((((Pointer)(heapStart)) <= ((Pointer)((((Pointer)((char *
)(e) + (-1))))))) && (((Pointer)((((Pointer)((char *)
(e) + (-1)))))) < ((Pointer)(heapEnd)))))
pgmapMod((Page *) pgMap, pgMapUses, PgPgMap);

return 1;
912}

914localstatic Page *
915pagesFind(Length npages)
916{
int i = pgmapFindFree(npages);
918/*         if (osGetEnv("GC_FINDFREE")!=NULL) { fprintf(osStderr, "Page Found %ld\n",i);}; */
return (i == -1) ? 0 : pgAt(i)((Page *)((Pointer)((char *)(heapStart) + ((i) * (1L<<12
)))));
920}

922localstatic Page *
923pagesGet(Length nMin)
924{
Page	*p;
Bool	addAnyway = false((int) 0);
Length	nBest = nMin;

p = pagesFind(nMin);

if (p) {
if (nMin > 0) pgmapMod(p,   1,      PgBusyFirst);
if (nMin > 1) pgmapMod(p+1, nMin-1, PgBusyFollow);
}
else if (gcLevel == StoCtl_GcLevel_Automatic2) {
int	tot, free0, free1;
int	gceLhs, gceRhs;

tot   = pgmapCountDomestic();
free0 = pgmapCountFree();
stoGc();
free1 = pgmapCountFree();


/* Are there sufficient free pages for this request? */
addAnyway = (nMin > free1);


/* If there are enough, is the headroom big enough? */
if (!addAnyway)
{
	/* Frugal or normal heap growth? */
	if (GcIsFrugal)
		addAnyway = stoNeedsMoreHeadroom(free1);
	else
	{
		gceLhs = GcEffectiveFactorNum * tot;
		gceRhs = GcEffectiveFactorDen * free1;
		addAnyway = (gceLhs > gceRhs);
	}
}

if (addAnyway &&
	(GcGrowthFactorNum * tot) > (GcGrowthFactorDen*(tot + nMin)))
{
	nBest = (Length) ((GcGrowthFactorNum - GcGrowthFactorDen ) * tot /GcGrowthFactorDen  + 1);
	nBest = nBest < GcMinGrowth ? GcMinGrowth : nBest;
}

p = pagesFind(nMin);
if (p) {
	if (nMin > 0) pgmapMod(p,   1,      PgBusyFirst);
	if (nMin > 1) pgmapMod(p+1, nMin-1, PgBusyFollow);
}

if (gcTraceFile) {
	fprintf(gcTraceFile, " [GC: %s enough, %d/%d -> %d/%d for " LENGTH_FMT"%lu" "]\n",
		p ? "!!! Got" : "... Not", free0, tot, free1, tot, nMin);

	if (addAnyway) {
		fprintf(gcTraceFile, "\n [GC: Growing heap (not enough %s)]\n",
			(nMin > free1) ? "free pages" : "headroom");
	}
}
985#ifdef FOAM_RTS 
if (markingStats) {
	fprintf(osStderr, " [GC: %s enough, %d/%d -> %d/%d for " LENGTH_FMT"%lu" "]\n",
		p ? "!!! Got" : "... Not", free0, tot, free1, tot, nMin);

	if (addAnyway) {
		fprintf(osStderr, "\n [GC: Growing heap (not enough %s)]\n",
			(nMin > free1) ? "free pages" : "headroom");
	}
}
995#endif 
}
if (!p || addAnyway)
pagesAdd(nBest, nMin);
if (!p) {
p = pagesFind(nMin);
if (p) {
	if (nMin > 0) pgmapMod(p,   1,      PgBusyFirst);
	if (nMin > 1) pgmapMod(p+1, nMin-1, PgBusyFollow);
}
}

return p;
1008}

1010localstatic void
1011pagesPut(Page *pg, Length count)
1012{
pgmapMod  (pg, count, PgFree);
freeFill(pg, count*PgSize)(stoMustWash ? memlset (pg,0xDD,count*(1L<<12)) : 0);
1015}

1017/*****************************************************************************
*
* :: Section manipulation
*
****************************************************************************/

1023struct Section {
short		pgCount;	/* Number of pages in section. */
short		qmLog;		/* base 2 log of size, if integral */
1026#ifdef STO_DIVISION_BY_LOOKUP1
UByte		qmDiv;		/* division table if !qmLog */
1028#endif
short		qmSize;		/* Alloc quantum. */
UByte		qmSizeIndex;	/* Index of quantum in size table. */
BPack(Bool)UByte	isFixed;	/* Alloc of same or different sizes? */

FxMem		*free;		/* Section free list (for stoTune). */
ULong		qmCount;	/* Number of quanta of data. */
Pointer		data;		/* Pointer to start of data. */
QmInfo		info[NARY10];	/* Per quantum information. */
1037};

1039#define SectionHeadSize(sizeof(Section) + (0) * sizeof(QmInfo) - 10 * sizeof(QmInfo)
) fullsizeof(Section, 0, QmInfo)(sizeof(Section) + (0) * sizeof(QmInfo) - 10 * sizeof(QmInfo)
)

1041/*
* Macros for maintaining the info array:
*   bits 0-4: object code
*   bit    5: mark bit
*   bits 6-7: kind of page
*/
1047#define QmKindMask0xC0	0xC0
1048#define	  QmFollow0x00	0x00
1049#define	  QmFreeFirst0x40	0x40
1050#define	  QmBusyFirst0x80	0x80
1051#define   QmBlacklisted0xC0	0xC0

1053#define QmMarkMask0x20	0x20
1054#define QmCodeMask0x1F	0x1F

1056#define QmInfoMake(kind, code)(((kind) & 0xC0) | ((code) & 0x1F))	(((kind) & QmKindMask0xC0) | ((code) & QmCodeMask0x1F))
1057#define QmInfoMake0(kind)(kind)	(kind)
1058#define QmInfoKind(info)((info) & 0xC0)	((info)	 & QmKindMask0xC0)
1059#define QmInfoCode(info)((info) & 0x1F)	((info)	 & QmCodeMask0x1F)
1060#define QmInfoMark(info)((info) & 0x20)	((info)	 & QmMarkMask0x20)

1062#define QmInfoSetKind(info,kind)((info) = ((info) & (~0xC0 & 0xFF)) | ((kind) & 0xC0
))((info) = \
((info) & (~QmKindMask0xC0 & 0xFF)) | ((kind) & QmKindMask0xC0))
1064#define QmInfoSetCode(info,code)((info) = ((info) & (~0x1F & 0xFF)) | ((code) & 0x1F
))((info) = \
((info) & (~QmCodeMask0x1F & 0xFF)) | ((code) & QmCodeMask0x1F))
1066#define QmInfoSetMark(info)((info) |= 0x20)	((info) |=  QmMarkMask0x20)
1067#define QmInfoClearMark(info)((info) &= (~0x20 & 0xFF))	((info) &= (~QmMarkMask0x20 & 0xFF))

1069#define QmIsPtrFree(info)(stoObNoInternalPtrs[((info) & 0x1F)])	(stoObNoInternalPtrs[QmInfoCode(info)((info) & 0x1F)])
1070#define QmAldorTraced(info)(stoObAldorTracer[((info) & 0x1F)])	(stoObAldorTracer[QmInfoCode(info)((info) & 0x1F)])
1071#define QmCTraced(info)(stoObCTracer[((info) & 0x1F)])		(stoObCTracer[QmInfoCode(info)((info) & 0x1F)])


1074/*
* Find the section into which p points.  0 indicates error. If you know
* that the section is the first (eg for fixed-size pages) then sectOf(p)
* is the most efficient method to use rather than sectAt(pgNo(p)).
*/
1079#ifdef STO_SECT_AND_PAGE_OF1
1080#define sectOf(p)((Section *)(((Pointer)((char *)(heapStart) + ((((long)((char
 *)(p) - (char *)(heapStart))) & ~((1L<<12)-1))))))
)  ((Section *)pgOf(p)(((Pointer)((char *)(heapStart) + ((((long)((char *)(p) - (char
 *)(heapStart))) & ~((1L<<12)-1)))))))
1081#else
1082#define sectOf(p)((Section *)(((Pointer)((char *)(heapStart) + ((((long)((char
 *)(p) - (char *)(heapStart))) & ~((1L<<12)-1))))))
)  sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))
1083#endif
1084#define sectAt(n)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((n) *
 (1L<<12))))))  ((Section *) pgAt(n)((Page *)((Pointer)((char *)(heapStart) + ((n) * (1L<<12
))))))
1085#define sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p)) (pgMap[pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12)]==PgBusyFirst ? sectAt(pgNo(p))((Section *) ((Page *)((Pointer)((char *)(heapStart) + (((((long
)((char *)((char *)(p)) - (char *)(heapStart))) >> 12))
 * (1L<<12)))))):_sectFor(p))

1087/*
* Given a pointer and a section, find the index into the info array.
*/
1090#define qmNo(p,sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize) (ptrDiff((char*)(p),(char*)((sect)->data))((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize)

1092#define qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog) (ptrDiff((char*)(p),(char*)((sect)->data))((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog)


1095/* For sections with fixed-sized pages, this is more efficient: */
1096#ifdef STO_DIVISION_BY_LOOKUP1
1097#define qmDivNo(p, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(p)) -
 (char *)((char*)((sect)->data)))))] stoDivTable[(sect)->qmDiv][(ptrDiff((char*)(p),(char*)((sect)->data))((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))))]
1098#endif


1101/*
* How many quanta will fit in a section with this many pages?
*/
1104localstatic Length
1105sectQmCount(Length pageCount, Length qmSize)
1106{
return (pageCount * PgSize(1L<<12) - SectionHeadSize(sizeof(Section) + (0) * sizeof(QmInfo) - 10 * sizeof(QmInfo)
))/(qmSize + sizeof(QmInfo));
1108}

1110/*
* Initialize the stretch of pages.
*/
1113localstatic Section *
1114sectPrepare(Page *p, Length npages, Length sz, int isFixed)
1115{
Section *x     = (Section *) p;
Length	szixix, i, nq;
int  lgWordSize;

lgWordSize = 0;
for (i = sizeof(Pointer); i > 1; i = i>>1) lgWordSize++;
assert(npages < (1<<16))do { if (!(npages < (1<<16))) _do_assert(("npages < (1<<16)"
),"store.c",1122); } while (0);
szixix	       = (sz <= FixedSizeMax(32*sizeof(Pointer))) ? sz : 0;
x->pgCount     = npages;
x->qmSize      = sz;
x->qmSizeIndex = fixedSizeIndexFor[szixix];
1127#ifdef STO_DIVISION_BY_LOOKUP1
x->qmLog       = fixedSizeLog[x->qmSizeIndex] < 0 
? 0 : fixedSizeLog[x->qmSizeIndex] + lgWordSize;
x->qmDiv       = x->qmLog ? 0 : -(fixedSizeLog[x->qmSizeIndex]+1);
1131#else
x->qmLog       = fixedSizeLog[x->qmSizeIndex] < 0 
? 0 : fixedSizeLog[x->qmSizeIndex] + lgWordSize;
1134#endif
x->isFixed     = isFixed;
x->qmCount     = nq = sectQmCount(npages, sz);
x->data	       = ptrOff((char *) p, npages * PgSize - nq * sz)((Pointer)((char *)((char *) p) + (npages * (1L<<12) - nq
 * sz)));

/*
* Fixed section is a whole bunch of little pieces.
* Mixed section contains one big one.
*/
if (stoMustTag) {
x->info[0] = QmInfoMake0(QmFreeFirst)(0x40);
if (isFixed)
	for (i = 1; i < nq; i++)
		x->info[i] = QmInfoMake0(QmFreeFirst)(0x40);
else
	for (i = 1; i < nq; i++)
		x->info[i] = QmInfoMake0(QmFollow)(0x00);
}
return x;
1153}

1155localstatic Section *
1156_sectFor(Pointer p)
1157{
Length	pi;

if (!isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))))
return 0;
pi = pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12);
while (pgMap[pi] == PgBusyFollow)
pi--;
if (pgMap[pi] == PgBusyFirst)
return sectAt(pi)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pi) *
 (1L<<12))))));
return 0;
1168}

1170/*****************************************************************************
*
* :: Fixed piece management
*
****************************************************************************/

1176struct FxMem {
struct FxMem	*next;
1178};

1180# define fxmemCleanHead(pc)(stoMustWash ? memlset ((UByte *)(pc),0xDD,sizeof(FxMem)) : 0
) \
freeFill  ((UByte *)(pc), sizeof(FxMem))(stoMustWash ? memlset ((UByte *)(pc),0xDD,sizeof(FxMem)) : 0
)
1182# define fxmemCleanBody(pc, sz)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(FxMem),0xDD,(sz
) - sizeof(FxMem)) : 0) \
freeFill  ((UByte *)(pc) + sizeof(FxMem), (sz) - sizeof(FxMem))(stoMustWash ? memlset ((UByte *)(pc) + sizeof(FxMem),0xDD,(sz
) - sizeof(FxMem)) : 0)
1184# define fxmemAssertCleanBody(pc, sz)(stoMustWash ? memltest((UByte *)(pc) + sizeof(FxMem),0xDD,(sz
) - sizeof(FxMem)) : 0) \
freeAssert((UByte *)(pc) + sizeof(FxMem), (sz) - sizeof(FxMem))(stoMustWash ? memltest((UByte *)(pc) + sizeof(FxMem),0xDD,(sz
) - sizeof(FxMem)) : 0)


1188localstatic FxMem *
1189piecesGetFixed(Length nbytes)
1190{
Page		*pages;
Section		*sect;
FxMem		*pieces, *pieces0;
Length		sz, i, npages, npieces;

npages	= FixedSizePgGroup1;
sz	= fixedSizeFor[nbytes];
pages	= pagesGet(npages);
if (!pages) return 0;

sect	= sectPrepare(pages, npages, sz, true1);

npieces = sect->qmCount;
pieces0 = (FxMem *) sect->data;

for (pieces = pieces0, i = 1; i < npieces; i++, pieces = pieces->next)
pieces->next = (FxMem *) ptrOff((char *) pieces, sz)((Pointer)((char *)((char *) pieces) + (sz)));
pieces->next = fixedPieces[fixedSizeIndexFor[nbytes]];

return pieces0;
1211}

1213/*****************************************************************************
*
* :: Mixed piece management
*
****************************************************************************/

1219typedef struct MxMemDLL {
ULong	nbytes;
MxMem	*pieces;
1222} MxMemDLL;

1224typedef union MxMemU {
struct {
MxMem		*linkA, *linkB;
MxMemDLL	*dll;
} free;
struct {
MostAlignedType	 data;
} busy;
1232} MxMemU;


1235struct MxMem {
ULong		nbytesPrev;
ULong		nbytesThis;
BPack(Bool)UByte	isFree;
BPack(Bool)UByte	isFirst;
BPack(Bool)UByte	isLast;
Section		*sect;

/* Gap */
union MxMemU	body;
1245};

1247#define MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU))	(sizeof(MxMem) - sizeof(MxMemU))

1249#define mxmemNext(p)((p)->isLast ? 0 : (MxMem *)((Pointer)((char *)((char *)(p
)) + ((long)(p)->nbytesThis)))) ((p)->isLast ? 0 : (MxMem *)ptrOff((char *)(p), (long)(p)->nbytesThis)((Pointer)((char *)((char *)(p)) + ((long)(p)->nbytesThis)
)))
1250#define mxmemPrev(p)((p)->isFirst? 0 : (MxMem *)((Pointer)((char *)((char *)(p
)) + (-(long)(p)->nbytesPrev)))) ((p)->isFirst? 0 : (MxMem *)ptrOff((char *)(p),-(long)(p)->nbytesPrev)((Pointer)((char *)((char *)(p)) + (-(long)(p)->nbytesPrev
))))


1253# define mxmemCleanHead0(pc)(stoMustWash ? memlset ((UByte *)(pc),0xDD,sizeof(MxMem)) : 0
) \
freeFill  ((UByte *)(pc), sizeof(MxMem))(stoMustWash ? memlset ((UByte *)(pc),0xDD,sizeof(MxMem)) : 0
)
1255# define mxmemCleanHead(pc)(stoMustWash ? memlset ((UByte *)(pc) + (sizeof(MxMem) - sizeof
(MxMemU)),0xDD,sizeof(MxMem) - (sizeof(MxMem) - sizeof(MxMemU
))) : 0) \
freeFill  ((UByte *)(pc) + MxMemHeadSize, sizeof(MxMem) - MxMemHeadSize)(stoMustWash ? memlset ((UByte *)(pc) + (sizeof(MxMem) - sizeof
(MxMemU)),0xDD,sizeof(MxMem) - (sizeof(MxMem) - sizeof(MxMemU
))) : 0)
1257# define mxmemCleanBody(pc, sz)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0) \
freeFill  ((UByte *)(pc) + sizeof(MxMem), (sz) - sizeof(MxMem))(stoMustWash ? memlset ((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0)
1259# define mxmemAssertCleanBody(pc, sz)(stoMustWash ? memltest((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0) \
freeAssert((UByte *)(pc) + sizeof(MxMem), (sz) - sizeof(MxMem))(stoMustWash ? memltest((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0)


1263#ifdef STO_LONGJMP
1264static jmp_buf	stoAllocInner_ErrorCatch;
1265static Pointer	stoAllocInner_ErrorValue;
1266#endif

1268localstatic FxMem *
1269stoAllocInner(ULong nbytes, PgKind pgkind)
1270{
int	i, npcs;
ULong	npages;
Page	*pages;
FxMem	*pcs0, *pcs;

npages	= 1;
assert(nbytes <= npages*PgSize)do { if (!(nbytes <= npages*(1L<<12))) _do_assert(("nbytes <= npages*PgSize"
),"store.c",1277); } while (0);
npcs  = (npages*PgSize(1L<<12))/nbytes;
pages = pagesGet(npages);

if (pages == 0) {
1282#ifdef STO_LONGJMP
stoAllocInner_ErrorValue = (*stoError)(StoErr_CantBuild3);
longjmp(stoAllocInner_ErrorCatch, int0((int) 0));
1285#else
(*stoError)(StoErr_CantBuild3);
NotReached(;){(void)bug("Not supposed to reach line %d in file: %s\n",1287
, "store.c");};
1288#endif
}

pgmapMod(pages, npages, pgkind);

pcs = pcs0 = (FxMem *) pages;
for (i = 1; i < npcs; i++)
pcs = pcs->next = (FxMem *) ptrCanon((char *) pcs+nbytes)((Pointer)((char *) pcs+nbytes));
pcs->next = 0;
return pcs0;
1298}

1300static FxMem	*btreeNodes = 0;
1301static FxMem	*mxmemDLLs  = 0;

1303BTree
1304mxmemAllocBTree(ULong nbytes)
1305{
BTree	b;

if (!btreeNodes) btreeNodes = stoAllocInner(nbytes, PgBTree);
b = (BTree) btreeNodes;
btreeNodes = btreeNodes->next;
return b;
1312}

1314void
1315mxmemFreeBTree(BTree b)
1316{
FxMem	*p = (FxMem *) b;
p->next	   = btreeNodes;
btreeNodes = p;
1320}

1322MxMemDLL *
1323mxmemAllocDLL(void)
1324{
MxMemDLL *p;

if (!mxmemDLLs) mxmemDLLs = stoAllocInner((ULong) sizeof(*p), PgDLL);
p = (MxMemDLL *) mxmemDLLs;
mxmemDLLs = mxmemDLLs->next;
return p;
1331}

1333void
1334mxmemFreeDLL(MxMemDLL *m)
1335{
FxMem	*p = (FxMem *) m;
p->next	   = mxmemDLLs;
mxmemDLLs  = p;
1339}

1341# define mxmemUnlinkFromBTree(mi, pbt){ MxMemDLL *dll = mxmemUnlink(mi); if ((!dll->pieces)) { btreeDeleteX
((pbt), dll->nbytes, ((void*)0), mxmemFreeBTree); mxmemFreeDLL
(dll); } } {				\
MxMemDLL *dll = mxmemUnlink(mi);				\
IF(!dll->pieces)if ((!dll->pieces)) {						\
btreeDeleteX((pbt), dll->nbytes, NULL((void*)0), mxmemFreeBTree);	\
mxmemFreeDLL(dll);					\
}								\
}

1349localstatic MxMemDLL *
1350mxmemUnlink(MxMem *mi)
1351{
MxMemDLL *dll = mi->body.free.dll;
MxMem	 *A   = mi->body.free.linkA,
 *B   = mi->body.free.linkB;

/* Remove from doubly linked list. */
IF (A)if ((A))  A->body.free.linkB = B;
IF (B)if ((B))  B->body.free.linkA = A;

/* Adjust pointer to the list.	Make null if no siblings. */
IF (ptrEQ(mi, dll->pieces))if ((( ((Pointer)((Pointer)(mi)) == (Pointer)((Pointer)(dll->
pieces)))))) 
dll->pieces = A ? A : B;

return dll;
1365}

1367/*
* Link a mixed-size piece into the B-tree.
*/
1370localstatic void
1371mxmemLink(MxMem *mi)
1372{
BTree		bnode;
int		bix;

mi    = (MxMem *) ptrCanon(mi)((Pointer)(mi)); /* For < comp  */
bnode = btreeSearchEQ(mixedPieces, mi->nbytesThis, &bix);

IF (bnode)if ((bnode)) {
MxMemDLL *dll = (MxMemDLL *) btreeElt(bnode, bix)((bnode)->part[bix].entry);
MxMem	 *u, *v;

/*!! Sorting by address can give bad paging with these DLLs. */
u = dll->pieces;
v = u->body.free.linkA;
WHILE (mi > u && v)while ((mi > u && v)) { u = v; v = u->body.free.linkA; }

mi->body.free.dll	  = dll;
mi->body.free.linkA	  = v;
mi->body.free.linkB	  = u;
u->body.free.linkA	  = mi;
IF (v)if ((v)) v->body.free.linkB = mi;
}
else {
1395#if 1
MxMemDLL *dll = mxmemAllocDLL();

dll->nbytes   = mi->nbytesThis;
dll->pieces   = mi;
btreeInsertX(&mixedPieces,
	     (BTreeKey) dll->nbytes, (BTreeElt) dll,
	     mxmemAllocBTree);

mi->body.free.dll   = dll;
mi->body.free.linkA = 0;
mi->body.free.linkB = 0;
1407#else
MxMemDLL *dll;
mi->body.free.linkA = 0;
mi->body.free.linkB = 0;
dll = mxmemAllocDLL();

dll->nbytes   = mi->nbytesThis;
dll->pieces   = mi;
btreeInsertX(&mixedPieces,
	     (BTreeKey) dll->nbytes, (BTreeElt) dll,
	     mxmemAllocBTree);

mi->body.free.dll   = dll;

1421#endif
}
1423}

1425/*
* Merge two adjacent pieces.
*/
1428localstatic void
1429mxmemMerge(MxMem *curr, MxMem *next)
1430{
MxMem	*N	     = mxmemNext(next)((next)->isLast ? 0 : (MxMem *)((Pointer)((char *)((char *
)(next)) + ((long)(next)->nbytesThis))));

curr->nbytesThis    += next->nbytesThis;
curr->isLast	     = next->isLast;
IF (N)if ((N)) N->nbytesPrev = curr->nbytesThis;

if (stoMustTag) {
QmInfo *pqm = next->sect->info + qmNo(next,next->sect)(((long)((char *)((char*)(next)) - (char *)((char*)((next->
sect)->data))))/(next->sect)->qmSize);
QmInfoSetKind(*pqm, QmFollow)((*pqm) = ((*pqm) & (~0xC0 & 0xFF)) | ((0x00) & 0xC0
));
}
mxmemCleanHead0(next)(stoMustWash ? memlset ((UByte *)(next),0xDD,sizeof(MxMem)) :
 0);
1442}

1444/*
* Return the remainder, where curr keeps only nbytes.
* nbytes must be a multiple of MixedSizeQuantum.
*/
1448localstatic MxMem *
1449mxmemSplit(MxMem *curr, ULong nbytes)
1450{
MxMem	*r	     = (MxMem *) ptrOff((char *)curr, nbytes)((Pointer)((char *)((char *)curr) + (nbytes)));
MxMem	*N	     = mxmemNext(curr)((curr)->isLast ? 0 : (MxMem *)((Pointer)((char *)((char *
)(curr)) + ((long)(curr)->nbytesThis))));

r->isFree	     = curr->isFree;
r->isFirst	     = false((int) 0);
r->isLast	     = curr->isLast;
r->nbytesThis	     = curr->nbytesThis - nbytes;
r->nbytesPrev	     = nbytes;
r->sect		     = curr->sect;

curr->isLast	     = false((int) 0);
curr->nbytesThis     = nbytes;

IF (N)if ((N)) N->nbytesPrev = r->nbytesThis;

if (stoMustTag) {
QmInfo *pqm = curr->sect->info + qmNo(r,curr->sect)(((long)((char *)((char*)(r)) - (char *)((char*)((curr->sect
)->data))))/(curr->sect)->qmSize);
QmInfoSetKind(*pqm, QmFreeFirst)((*pqm) = ((*pqm) & (~0xC0 & 0xFF)) | ((0x40) & 0xC0
));
}
return r;
1471}

1473localstatic MxMemDLL *
1474mxmemShow(MxMemDLL *dll)
1475{
int	n;
MxMem	*t;

/* Make t point to A-most piece. */
t = dll->pieces;
while (t->body.free.linkA)
t = t->body.free.linkA;
/* Count the pieces */
for (n = 0; t; n++) {
if (t->nbytesThis != dll->nbytes)
	fprintf(osStderr, "(%ld)", t->nbytesThis);
t = t->body.free.linkB;
}
fprintf(osStderr," %dx%ld", n, dll->nbytes);

return dll;
1492}

1494void
1495piecePutMixed(MxMem *mi)
1496{
MxMem		*prev, *next;

if (!mixedPieces) mixedPieces = btreeNewX(MixedBTreeT16, mxmemAllocBTree);


/* 1. Determine which adjacent pieces will be merged. */
prev = mxmemPrev(mi)((mi)->isFirst? 0 : (MxMem *)((Pointer)((char *)((char *)(
mi)) + (-(long)(mi)->nbytesPrev))));
IF (prev && !prev->isFree)if ((prev && !prev->isFree)) prev = 0;
next = mxmemNext(mi)((mi)->isLast ? 0 : (MxMem *)((Pointer)((char *)((char *)(
mi)) + ((long)(mi)->nbytesThis))));
IF (next && !next->isFree)if ((next && !next->isFree)) next = 0;

/* 2. Remove those pieces from the piece tree and merge. */
IF (next)if ((next)) {
mxmemUnlinkFromBTree(next, &mixedPieces){ MxMemDLL *dll = mxmemUnlink(next); if ((!dll->pieces)) {
 btreeDeleteX((&mixedPieces), dll->nbytes, ((void*)0),
 mxmemFreeBTree); mxmemFreeDLL(dll); } };
mxmemMerge(mi, next);
}

IF (prev)if ((prev)) {
mxmemUnlinkFromBTree(prev, &mixedPieces){ MxMemDLL *dll = mxmemUnlink(prev); if ((!dll->pieces)) {
 btreeDeleteX((&mixedPieces), dll->nbytes, ((void*)0),
 mxmemFreeBTree); mxmemFreeDLL(dll); } };
mxmemMerge(prev, mi);
mi = prev;
}

/* 3. Add piece to piece tree. */
mxmemLink(mi);

/* 4. We're free */
mi->isFree = true1;

1526}

1528/*
* Get the best piece with size at least nbytes from the mixed piece pool.
* nbytes is guaranteed to be a multiple of MixedSizeQuantum.
*
* Keeping mixedFrontier out of mixedPieces btree avoids one btreeDelete
* and one btreeInsert each time it is used.
*/

1536#define shdSplit1(nhas, nreq)((nhas) > (nreq) + (32*sizeof(Pointer))) ((nhas) > (nreq) + MixedSizeQuantum(32*sizeof(Pointer)))
1537#define shdSplit2(nhas,nreq)((nhas) > (nreq) + (32*sizeof(Pointer)))  ((nhas) > (nreq) + MixedSizeQuantum(32*sizeof(Pointer)))
1538#define shdBe1(nhas,nreq)(nreq)     (nreq)
1539#define shdBe2(nhas,nreq)(nreq)     (nreq)

1541MxMem *
1542pieceGetMixed(ULong nbytes)
1543{
BTree		bnode, bnode1;
int		bix, bix1;
MxMem		*mi, *mt, *tmp;
MxMemDLL	*dll;
Bool		is1;
ULong		mn;

if (!mixedPieces) mixedPieces = btreeNewX(MixedBTreeT16, mxmemAllocBTree);


/* First check in mixed-size pieces free tree. */
bnode = btreeSearchGE(mixedPieces, nbytes, &bix);
IF (bnode)if ((bnode)) {
mi	   = ((MxMemDLL *) btreeElt(bnode, bix)((bnode)->part[bix].entry))->pieces;
dll	   = mxmemUnlink(mi);
is1	   = !dll->pieces;
mi->isFree = false((int) 0);

mn = mi->nbytesThis;
IF (shdSplit1(mn, nbytes))if ((((mn) > (nbytes) + (32*sizeof(Pointer))))) {
	ULong r = mi->nbytesThis - nbytes;

	mt = mxmemSplit(mi,shdBe1(mn, nbytes)(nbytes));
	mt->isFree = true1;
	bnode1 = !is1 ? 0 : btreeSearchGE(mixedPieces,r,&bix1);

	IF (!is1)if ((!is1)) {
		piecePutMixed(mt);
	}
	else IF (bnode1 != bnode || bix1 != bix)if ((bnode1 != bnode || bix1 != bix)) {
		btreeDeleteX(&mixedPieces, dll->nbytes, NULL((void*)0),
			     mxmemFreeBTree);
		mxmemFreeDLL(dll);
		piecePutMixed(mt);
	}
	else {
		/* Reuse btree entry. */
		btreeKey(bnode1, bix1)((bnode1)->part[bix1].key) = r;
		dll->nbytes = r;
		dll->pieces = mt;
		mt->body.free.linkA = mt->body.free.linkB = 0;
		mt->body.free.dll   = dll;
	}
}
else IF (is1)if ((is1)) {
	btreeDeleteX(&mixedPieces, dll->nbytes, NULL((void*)0),
		     mxmemFreeBTree);
	mxmemFreeDLL(dll);
}
}
else {
/* no piece in mixed-size free tree is big enough. */
IF (mixedFrontier && mixedFrontier->nbytesThis < nbytes)if ((mixedFrontier && mixedFrontier->nbytesThis <
 nbytes)) {
	/* Frontier piece is too small. Thow it away. */
	tmp = mixedFrontier;
	mixedFrontier = 0;
	piecePutMixed(tmp);
	stoWatchFrontier(tmp);
	/* (Actually, this could have lead to a merge). */
}

IF (!mixedFrontier)if ((!mixedFrontier)) {
	/* Need a new frontier piece to satisfy request. */
	Length	npages;
	ULong	nq, nb;
	Page	*pages;
	Section *sect;

	nq = QUO_ROUND_UP(nbytes, MixedSizeQuantum)((nbytes) % ((32*sizeof(Pointer))) ? (nbytes)/((32*sizeof(Pointer
))) + 1 : (nbytes)/((32*sizeof(Pointer))));
	nb = SectionHeadSize(sizeof(Section) + (0) * sizeof(QmInfo) - 10 * sizeof(QmInfo)
) +
	     nq * (sizeof(QmInfo) + MixedSizeQuantum(32*sizeof(Pointer)));
	npages = QUO_ROUND_UP(nb, PgSize)((nb) % ((1L<<12)) ? (nb)/((1L<<12)) + 1 : (nb)/(
(1L<<12)));

	IF (npages < MixedSizePgGroup)if ((npages < 2))
		npages = MixedSizePgGroup2;

	pages = pagesGet(npages);
	if (!pages) return 0;

	sect  = sectPrepare(pages, npages,
			    (Length) MixedSizeQuantum(32*sizeof(Pointer)), false((int) 0));

	mt	       = (MxMem *) sect->data;
	mt->isFree     = false((int) 0); /* so free won't merge+unlink */
	mt->isFirst    = true1;
	mt->isLast     = true1;
	mt->nbytesPrev = 0;
	mt->nbytesThis = sect->qmCount * MixedSizeQuantum(32*sizeof(Pointer));
	mt->sect       = sect;

	mixedFrontier = mt;
	stoWatchFrontier(mixedFrontier);
}

mi = mixedFrontier;
mi->isFree = false((int) 0);

mn = mixedFrontier->nbytesThis;

IF (shdSplit2(mn, nbytes))if ((((mn) > (nbytes) + (32*sizeof(Pointer)))))
	mixedFrontier = mxmemSplit(mi, shdBe2(mn, nbytes)(nbytes));
else 
	mixedFrontier = 0;

stoWatchFrontier(mixedFrontier);
}
return mi;
1651}

1653/****************************************************************************
*
* :: Garbage collector
*
***************************************************************************/

1659/*
* This draft assumes that all words can be pointers.
*   The type code could be used to avoid following things which are known
*   not to be pointers.
*
* Pointers into the middle of structures are properly recognized.
*/

1667localstatic void	stoGcMarkAndSweep (void);
1668localstatic int	stoGcMark	  (void);
1669localstatic int	stoGcMarkRange	  (Pointer *lo, Pointer *hi, int check);
1670localstatic int	stoGcSweep	  (void);
1671localstatic int	stoGcSweepFixed	  (Section *);
1672localstatic int	stoGcSweepMixed	  (Section *);

1674static int	stoGcMarkedFree;

1676localstatic Bool
1677stoNeedsMoreHeadroom(int npgFree)
1678{
int	i;
ULong	gceLhs, gceRhs;
ULong	nFree, nBusy, nPer;
ULong	nSpare, nAvail, nTotal;


/* Check the headroom for each size of fixed-size pieces */
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++)
{
/* Compute free/busy/spare counts */
nFree  = freeFixedPieces[i];
nBusy  = busyFixedPieces[i];
nPer   = sectQmCount(1L, fixedSize[i]);
nSpare = nPer*npgFree;
nAvail = nFree + nSpare;
nTotal = nBusy + nAvail;


/* Headroom ratios (don't want any FPE's) */
gceLhs = GcEffectiveFactorNum*nTotal;
gceRhs = GcEffectiveFactorDen*nAvail;


/* Stop if not enough headroom */
if (gceLhs > gceRhs) return true1;
}


/* Compute mixed-size usage */
nSpare = npgFree*(PgSize(1L<<12) - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU)));
nAvail = nSpare + freeMixedBytes;
nTotal = nAvail + busyMixedBytes;


/* Headroom ratios */
gceLhs = GcEffectiveFactorNum*nTotal;
gceRhs = GcEffectiveFactorDen*nAvail;


/* Do we have enough mixed-sized headroom? */
return (gceLhs > gceRhs);
1720}

1722/*
* Entry point to garbage collector.
* Use setjmp to force registers onto stack, then mark from roots.
*/

1727localstatic void
1728stoGcMarkAndSweep(void)
1729{
jmp_buf jb;
int	nm, ns;

setjmp(jb)_setjmp (jb);

if (gcTraceFile) {
fprintf(gcTraceFile, " [GC: ");
fflush(gcTraceFile);
}
1739#ifdef FOAM_RTS
if (markingStats) {
 fprintf(osStderr, " [GC: ");
 fflush(osStderr);
}
1744#endif 


1747#ifdef STO_LONGJMP
if (!setjmp(stoAllocInner_ErrorCatch)_setjmp (stoAllocInner_ErrorCatch)) return;
1749#endif

nm = stoGcMark();
ns = stoGcSweep();

if (gcTraceFile) {
fprintf(gcTraceFile, "marked %d (+ %d free), swept  %d.]\n",
	nm, stoGcMarkedFree, ns);
}
1758#ifdef FOAM_RTS
if (markingStats) fprintf(osStderr, "marked %d (+ %d free), swept  %d.]\n",
	nm, stoGcMarkedFree, ns);
1761#endif 
1762}


1765/* Pointer classification: DO NOT change the order of these defines! */
1766#define MEM_HEAP0  0
1767#define MEM_IDATA1 1
1768#define MEM_STACK2 2
1769#define MEM_DDATA3 3
1770#define MEM_MAX_TYPE(3 +1) (MEM_DDATA3+1)

1772#define PTR_INTO_HEAP0 0
1773#define PTR_INTO_BUSY1 1
1774#define PTR_INTO_DATA2 2
1775#define PTR_INTO_NEW3  3
1776#define PTR_INTO_FREE4 4
1777#define PTR_MAX_TYPE(4 +1) (PTR_INTO_FREE4+1)

1779static int stoMarkArea, stoMarkChildren;
1780static long stoMarkCount[2*MEM_MAX_TYPE(3 +1)][PTR_MAX_TYPE(4 +1)];

1782static char *
1783stoMarkCountArea(int i)
1784{
if (i >= MEM_MAX_TYPE(3 +1))
{
switch (i - MEM_MAX_TYPE(3 +1))
{
   case MEM_HEAP0  : return "(*)  Heap";
   case MEM_IDATA1 : return "(*) Idata";
   case MEM_DDATA3 : return "(*) Ddata";
   case MEM_STACK2 : return "(*) Stack";
   default        : return "(*)  ????";
}
}
else
{
switch (i)
{
   case MEM_HEAP0  : return "     Heap";
   case MEM_IDATA1 : return "    Idata";
   case MEM_DDATA3 : return "    Ddata";
   case MEM_STACK2 : return "    Stack";
   default        : return "     ????";
}
}
1807}

1809static char *
1810stoMarkCountTest(int i)
1811{
switch (i)
{
  case PTR_INTO_HEAP0 : return "Heap";
  case PTR_INTO_BUSY1 : return "Busy";
  case PTR_INTO_DATA2 : return "Data";
  case PTR_INTO_NEW3  : return " New";
  case PTR_INTO_FREE4 : return "Free";
  default            : return "????";
}
1821}

1823/*
* Mark the pieces currently in use.
* Use the stack, static data, and foreign dynamic data as roots.
* Return the number of busy pieces marked.
*/

1829localstatic int
1830stoGcMark(void)
1831{
struct osMemMap **mm;
int	n;
int i, j;
static int doClassify = -1;

mm = osMemMap(OSMEM_STACK0x04 | OSMEM_IDATA0x01 | OSMEM_DDATA0x02);
if (!mm) return 0;

/* Pointer classification only available in debug version */
if (DEBUG(sto)((int) 0)) {
if (doClassify == -1)
	doClassify = (osGetEnv("GC_CLASSIFY") != NULL((void*)0));

if (doClassify)
{
	/* Clear the classification tables */
	for (i = 0;i < (2*MEM_MAX_TYPE(3 +1));i++)
		for (j = 0;j < PTR_MAX_TYPE(4 +1);j++)
			stoMarkCount[i][j] = 0;
}
}

stoGcMarkedFree = 0;
n  = 0;

for ( ; (*mm)->use != OSMEM_END0x00; mm++) {
if (DEBUG(sto)((int) 0)) {
	/* Memory type being traced (for classification) */
	stoMarkArea	= MEM_HEAP0;
	stoMarkChildren = 0;
}

switch ((*mm)->use) {
case OSMEM_STACK0x04:
	if (DEBUG(sto)((int) 0)) {stoMarkArea++;}
	/* Fall through */
case OSMEM_IDATA0x01:
	if (DEBUG(sto)((int) 0)) {stoMarkArea++;}
	/*
	 * Top-level call to stoGcMarkRange requires
	 * page check under Win98.
	 */
	n += stoGcMarkRange((Pointer *)((*mm)->lo),
			    (Pointer *)((*mm)->hi), 1);

/* Some compilers, e.g. Watcom, define 1 byte aligned
 * pointers even packing structures with a 4 bytes alignment.
 */
1880#if defined(CC_one_byte_aligned_pointers)
	{
	    int i;
	    for (i = 1; i < sizeof(char*); i++)
		n += stoGcMarkRange(
			(Pointer *)ptrOff((*mm)->lo, i)((Pointer)((char *)((*mm)->lo) + (i))),
			(Pointer *)((*mm)->hi), 1);
	}
1888#endif /* CC_one_byte_aligned_pointers_ */

	break;
case OSMEM_DDATA0x02: {
1892#if defined(OS_WIN32)
	/*
	 * We have to be careful - this segment may contain
	 * just part of the heap.
	 */
	char *p;
	int  i, inbottom = 0, intop = 0;

	if (DEBUG(sto)((int) 0)) {stoMarkArea = MEM_DDATA3;}

	/* Scan from (*mm)->lo to heapStart? */
	if ((Pointer)heapStart >= (*mm)->lo &&
		(Pointer)heapStart < (*mm)->hi)
	{
	  inbottom = 1;
	  n += stoGcMarkRange((Pointer *)((*mm)->lo),
			      (Pointer *)(heapStart), 1);
	}

	/* Scan from heapEnd to (*mm)->hi? */
	if ( (Pointer)heapEnd >= (*mm)->lo &&
		(Pointer)heapEnd < (*mm)->hi)
	{
	  intop = 1;
	  n += stoGcMarkRange((Pointer *)(heapEnd),
			      (Pointer *)((*mm)->hi), 1);
	}

	/* If the heap is in the segment, scan foreign pages */
	if (inbottom || intop)
	{
	  /* Compute start and finish page */
	  int first = inbottom ? 0 : pgNo((Pointer)(*mm)->lo)(((long)((char *)((char *)((Pointer)(*mm)->lo)) - (char *)
(heapStart))) >> 12);
	  int last = intop ? pgMapSize : pgNo((Pointer)(*mm)->hi)(((long)((char *)((char *)((Pointer)(*mm)->hi)) - (char *)
(heapStart))) >> 12);

	  /* Scan foreign pages in heap in the segment */
	  for (i = first; i < last; i++) {
	    if (pgMap[i] != PgForeign) continue;
	    p = (char *) pgAt(i)((Page *)((Pointer)((char *)(heapStart) + ((i) * (1L<<12
)))));
	    n += stoGcMarkRange((Pointer *)(p),
				(Pointer *)(p+PgSize(1L<<12)), 1);
	  }
	}
	else {
	  /* Scan the whole segment */
	  n += stoGcMarkRange((Pointer *)((*mm)->lo),
			      (Pointer *)((*mm)->hi), 1);
	}
1940#else
	/*
	 * Assume that if heapStart lies within this
	 * segment then heapEnd does also.
	 */
	int  i;
	char *p;

	if (DEBUG(sto)((int) 0)) {stoMarkArea = MEM_DDATA3;}
	if ( (Pointer) heapStart >= (*mm)->lo &&
		(Pointer) heapStart < (*mm)-> hi)
	{
	  n += stoGcMarkRange((Pointer *)((*mm)->lo),
			      (Pointer *)(heapStart), 1);
	  n += stoGcMarkRange((Pointer *)(heapEnd),
			      (Pointer *)((*mm)->hi),1 );
	  
1957#if defined(OS_MAC_OSX)
            /*
              DGC:
              On Mac OS X the heap is not necessarily contiguous.
              There may be PgForeign pages, but there may also be
              gaps in VM.  Avoid trying to mark non-existent memory.
            
              I suspect that this may be a bug for other systems
              too,  and the fix should work for any system, but
              I'll leave it OS_MAC_OSX specific for now.                
            */
	  int mm_hi_pgNo = pgNo((*mm)->hi)(((long)((char *)((char *)((*mm)->hi)) - (char *)(heapStart
))) >> 12) ;
            int iMax =  (mm_hi_pgNo<pgMapSize) ? mm_hi_pgNo : pgMapSize ;
            for (i = 0; i < iMax; i++) {
	    p = (char *) pgAt(i)((Page *)((Pointer)((char *)(heapStart) + ((i) * (1L<<12
)))));
              n += stoGcMarkRange((Pointer *)(p),
				(Pointer *)(p+PgSize(1L<<12)), 1    );
	  }
1975#else  /* !defined(OS_MAC_OSX) */
	  for (i = 0; i < pgMapSize; i++) {
	    if (pgMap[i] != PgForeign) continue;
	    p = (char *) pgAt(i)((Page *)((Pointer)((char *)(heapStart) + ((i) * (1L<<12
)))));
	    n += stoGcMarkRange((Pointer *)(p),
				(Pointer *)(p+PgSize(1L<<12)), 1    );
	  }
1982#endif  /* defined(OS_MAC_OSX) */
	}
	else {
	  n += stoGcMarkRange((Pointer *)((*mm)->lo),
			      (Pointer *)((*mm)->hi), 1);
	}
1988#endif
	break;

  }
  default:
	assert(false)do { if (!(((int) 0))) _do_assert(("false"),"store.c",1993); }
 while (0); /*mem type is silly*/
	break;
}
}

/* Emit pointer classification table? */
if (DEBUG(sto)((int) 0)) {
if (doClassify)
{
	/* Column headings */
	fprintf(osStderr, "\n           ");
	for (j = 0;j < PTR_MAX_TYPE(4 +1);j++)
		fprintf(osStderr,"%10s ",stoMarkCountTest(j));


	/* Table contents */
	fprintf(osStderr, "\n");
	for (i = 0;i < (2*MEM_MAX_TYPE(3 +1));i++)
	{
		fprintf(osStderr, "%s: ", stoMarkCountArea(i));
		for (j = 0;j < PTR_MAX_TYPE(4 +1);j++)
		{
			long c = stoMarkCount[i][j];
			fprintf(osStderr,"%10ld ", c);
		}
		fprintf(osStderr, "\n");
	}

	/* Leave a gap below the table */
	fprintf(osStderr, "\n\n");
}
}

return n;
2027}

2029static int lvl;
2030localstatic int stoGcMarkRange1(Pointer *lo, Pointer *hi, int check);
2031localstatic int
2032stoGcMarkRange(Pointer *lo, Pointer *hi, int check)
2033{
lvl++;
if (DEBUG(sto)((int) 0) && lvl % 3000 == 0) {
printf("Deep stack %d\n", lvl);
}

int ret = stoGcMarkRange1(lo, hi, check);
lvl--;
return ret;
2042}

2044localstatic int
2045stoGcMarkRange1(Pointer *lo, Pointer *hi, int check)
2046{
Pointer		p, *pp, *plo, *phi, *hi0;
static int	pgno, qmno;
static PgInfo	pgtag;
static QmInfo	qmtag;
static Section *sect;
int		n = 0;
int		oldStoMarkArea;
2054#if defined(OS_WIN32)
MEMORY_BASIC_INFORMATION minfo;
int access;
2057#endif

2059#ifdef STO_CAN_BLACKLIST
static int	canBlacklist = -1;

if (canBlacklist == -1)
canBlacklist = (osGetEnv("GC_BLACKLIST") != NULL((void*)0));
2064#endif

2066#if defined(OS_WIN32)
/*
* Under Win98 and probably Win95 too, pages that were accessible
* during the call to osMemMap may now be inaccessible. Some pages
* are decommitted, some are released and some have their access
* permissions changed. Without this check we get a segfault or GPF.
*
* We daren't put this code in a procedure because the pages might
* be on the stack and be unmapped on return.
*
* ASSUMES that if the first page is still valid, the rest are ...
*/
if (!check) goto PagesOkay; /* Page range known to be safe (in heap) */

if (VirtualQuery((void *)lo, &minfo, sizeof(minfo)) != sizeof(minfo))
return n; /* Query failed => don't risk scanning the page */

/* First check the page type */
switch (minfo.State)
{
  case MEM_COMMIT:
/* These pages are okay. */
break;
  case MEM_FREE: /* FALL THROUGH */
(void)fprintf(stderrstderr, "*** committed -> free\n");
(void)fflush(stderrstderr);
return n;
  case MEM_RESERVE: /* FALL THROUGH */
/* These pages are definitely not okay. */
2095#if 0		
(void)fprintf(stderrstderr, "*** committed -> reserved\n");
(void)fflush(stderrstderr);
2098#endif
return n;
2100#if 0
  case MEM_MAPPED:
/* These pages might be okay. */
break;
  case MEM_PRIVATE:
/* These pages might be okay. */
break;
2107#endif
  default:
(void)fprintf(stderrstderr, "*** Unknown page type\n");
(void)fflush(stderrstderr);
/* Unknown page type: might be okay. */
break;
}

/*
* Check the state of the page ignoring guard and cache status. We
* want to skip any page that we cannot read from or write to. If we
* were paranoid then we only skip pages we cannot read.
*/
access = minfo.Protect & ~(PAGE_GUARD | PAGE_NOCACHE);
switch (access)
{
  case PAGE_NOACCESS:
/* Cannot scan this page even if it holds pointers */
(void)fprintf(stderrstderr, "*** read/write -> no access\n");
(void)fflush(stderrstderr);
return n;
  case PAGE_READONLY:
  case PAGE_EXECUTE:
  case PAGE_EXECUTE_READ:
/* Hope it doesn't contain pointers: try the next region. */
(void)fprintf(stderrstderr, "*** read/write -> read/exec\n");
(void)fflush(stderrstderr);
return n;
  case PAGE_READWRITE:
  case PAGE_WRITECOPY:
  case PAGE_EXECUTE_READWRITE:
  case PAGE_EXECUTE_WRITECOPY:
  case PAGE_WRITECOMBINE:
/* Might contain pointers so scan them. */
break;
  default:
/* Ignore this region in case it is something nasty. */
(void)fprintf(stderrstderr, "*** read/write -> ??? [%d]\n", access);
(void)fflush(stderrstderr);
return n;
}

/* We get here if the page check passed or wasn't needed */
2150PagesOkay: {}
2151#endif

/* Pointer classification */
if (DEBUG(sto)((int) 0)) {oldStoMarkArea = stoMarkArea;}

stoWatchMarkFrom(lo);
stoWatchMarkTo  (hi);

TailRecursion:
hi  = (Pointer *) ptrCanon(hi)((Pointer)(hi));
hi0 = (Pointer *) ptrOff(((char *) hi), 1 - sizeof(char *))((Pointer)((char *)(((char *) hi)) + (1 - sizeof(char *))));

for (pp = lo; ptrLT(pp, hi0)(((Pointer)(pp)) < ((Pointer)(hi0)));
    pp = (Pointer *) ptrOff((char *) pp, alignof(Pointer))((Pointer)((char *)((char *) pp) + ((sizeof(struct {char a; Pointer
 b;}) - sizeof(Pointer)))))) {
p = *pp;

/* Verify pointer is into heap. */
if (!isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd))))) continue;
if (DEBUG(sto)((int) 0)) {stoMarkCount[stoMarkArea][PTR_INTO_HEAP0]++;}


/* Verify pointer is to busy page. */
pgno  = pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12);
pgtag = pgMap[pgno];
if (pgtag != PgBusyFirst && pgtag != PgBusyFollow) continue;
if (DEBUG(sto)((int) 0)) {
	stoMarkCount[stoMarkArea][PTR_INTO_HEAP0]--;
	stoMarkCount[stoMarkArea][PTR_INTO_BUSY1]++;
}


/* Grab section header. */
while (pgtag == PgBusyFollow) pgtag = pgMap[--pgno];
sect = sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));

/* Verify pointed-to quantum. */
if (ptrLT(p, sect->data)(((Pointer)(p)) < ((Pointer)(sect->data)))) continue;
if (DEBUG(sto)((int) 0)) {
	stoMarkCount[stoMarkArea][PTR_INTO_BUSY1]--;
	stoMarkCount[stoMarkArea][PTR_INTO_DATA2]++;
}


2194#ifdef STO_DIVISION_BY_LOOKUP1
/* If interior of object, point to beginning. */
/* Use shift operations where possible */
if (sect->isFixed) {
	if (sect->qmLog) {
		qmno = qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog);
		p = ptrOff((char *) sect->data, qmno << sect->qmLog)((Pointer)((char *)((char *) sect->data) + (qmno << sect
->qmLog)));
	}
	else {
		qmno  = qmDivNo(p, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(p)) -
 (char *)((char*)((sect)->data)))))];
		assert(qmno == qmNo(p, sect))do { if (!(qmno == (((long)((char *)((char*)(p)) - (char *)((
char*)((sect)->data))))/(sect)->qmSize))) _do_assert(("qmno == qmNo(p, sect)"
),"store.c",2204); } while (0);
		p = ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
	}
}
else {
	qmno  = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
	p = ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
}
2212#else
/* If interior of object, point to beginning. */
/* Use shift operations where possible */
if (sect->isFixed && sect->qmLog) {
	qmno = qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog);
	p = ptrOff((char *) sect->data, qmno << sect->qmLog)((Pointer)((char *)((char *) sect->data) + (qmno << sect
->qmLog)));
}
else {
	qmno  = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
	/* If interior of object, point to beginning. */
	p = ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
}
2224#endif

/* Verify not already marked. */
qmtag = sect->info[qmno];
if (QmInfoMark(qmtag)((qmtag) & 0x20)) continue;
if (DEBUG(sto)((int) 0)) {
	stoMarkCount[stoMarkArea][PTR_INTO_DATA2]--;
	stoMarkCount[stoMarkArea][PTR_INTO_NEW3]++;
}


/* Add mark bits quanta in piece.  Determine data bounds. */
if (sect->isFixed) {
	QmInfoSetMark(sect->info[qmno])((sect->info[qmno]) |= 0x20);
	plo = (Pointer *) p;
	phi = (Pointer *) ptrOff((char *) plo, sect->qmSize)((Pointer)((char *)((char *) plo) + (sect->qmSize)));
}
else {
	MxMem	*pc;
	int	sz, nq, qi;

	while (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmFollow0x00)
		qmtag = sect->info[--qmno];

	pc = (MxMem *)ptrOff((char *)sect->data,((Pointer)((char *)((char *)sect->data) + (qmno*sect->qmSize
)))
			     qmno*sect->qmSize)((Pointer)((char *)((char *)sect->data) + (qmno*sect->qmSize
)));
	sz = pc->nbytesThis;
	nq = sz/sect->qmSize;

	for (qi = qmno; qi < qmno + nq; qi++)
		QmInfoSetMark(sect->info[qi])((sect->info[qi]) |= 0x20);

	sz -= MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU));
	plo = (Pointer *) (&pc->body.busy.data);
	phi = (Pointer *) ptrOff((char *) plo, sz)((Pointer)((char *)((char *) plo) + (sz)));
}

/* Verify piece is in use. */
if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmFreeFirst0x40) {
	if (DEBUG(sto)((int) 0)) {
		stoMarkCount[stoMarkArea][PTR_INTO_NEW3]--;
		stoMarkCount[stoMarkArea][PTR_INTO_FREE4]++;
	}
	stoGcMarkedFree++;

2269#ifdef STO_CAN_BLACKLIST
	/* We only blacklist fixed-sized pages currently */
	if (canBlacklist && sect->isFixed)
		sect->info[qmno] = QmInfoMake0(QmBlacklisted)(0xC0);
2273#endif
	continue;
}

2277#ifdef STO_CAN_BLACKLIST
if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBlacklisted0xC0) continue;
2279#endif
n++;

/* Check that this contains pointers 
 * This test should use a bit in the tag, not the code.
 */
if (QmIsPtrFree(qmtag)(stoObNoInternalPtrs[((qmtag) & 0x1F)])) continue;


2288#if STO_USER_CAN_TRACE
/*
 * Has the creator of this object requested
 * permission to trace it?
 */
if (QmAldorTraced(qmtag)(stoObAldorTracer[((qmtag) & 0x1F)]))
{
	/* Invoke the creator's tracer */
	n += (int)stoFiCCall2(int, QmAldorTraced(qmtag),((*((int (*)())((stoObAldorTracer[((qmtag) & 0x1F)]))->
prog->fun))(((stoObAldorTracer[((qmtag) & 0x1F)]))->
env,plo,phi))
		plo, phi)((*((int (*)())((stoObAldorTracer[((qmtag) & 0x1F)]))->
prog->fun))(((stoObAldorTracer[((qmtag) & 0x1F)]))->
env,plo,phi));
	continue;
}
if (QmCTraced(qmtag)(stoObCTracer[((qmtag) & 0x1F)]))
{
	/* Invoke the creator's tracer */
	n += (QmCTraced(qmtag)(stoObCTracer[((qmtag) & 0x1F)]))(plo, phi);
	continue;
}
2306#endif

/* Mark descendants. */
if (ptrEQ(pp, hi-1)( ((Pointer)((Pointer)(pp)) == (Pointer)((Pointer)(hi-1))))) {
	if (DEBUG(sto)((int) 0)) {
		if (stoMarkArea < MEM_MAX_TYPE(3 +1)) {
			/* Now marking within heap */
			oldStoMarkArea = stoMarkArea;
			stoMarkArea += MEM_MAX_TYPE(3 +1);
		}
	}

	lo = plo;
	hi = phi;
	goto TailRecursion;
}

/* Pointer classification */
if (DEBUG(sto)((int) 0)) {
	if (stoMarkArea < MEM_MAX_TYPE(3 +1)) {
		/* Now marking within heap */
		oldStoMarkArea = stoMarkArea;
		stoMarkArea += MEM_MAX_TYPE(3 +1);
	}
}

n += stoGcMarkRange(plo, phi, (int) 0);

/* Pointer classification */
if (DEBUG(sto)((int) 0)) {stoMarkArea = oldStoMarkArea;}
}

/* Pointer classification */
if (DEBUG(sto)((int) 0)) {stoMarkArea = oldStoMarkArea;}
return n;
2341}

2343/*
* Collect unmarked busy pieces.
* The small piece free lists are reconstructed, sorted by section.
*/

2348static FxMem	fixedHeadStruct[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))], *fixedTail[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
2349static ULong	freeFixedStruct[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
2350static ULong	busyFixedStruct[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];

2352localstatic int
2353stoGcSweep(void)
2354{
int	cd, ix, pgno, pgcount, swept, got;
Section *sect;

2358#ifdef USE_MEMORY_CLIMATE
initMemoryClimateHistogram();
2360#endif

for (cd = 0; cd < STO_CODE_LIMIT32; cd++)
stoPiecesGc[cd] = 0;	/* Tally by code of pieces swept. */

/* Reset the fixed-sized free lists and counters. */
for (ix = 0; ix < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); ix++)
{
fixedTail[ix] = &fixedHeadStruct[ix];

freeFixedStruct[ix] = 0L;
busyFixedStruct[ix] = 0L;
}


/* Reset the mixed-sized store counting */
freeMixedBytes = 0L;
busyMixedBytes = 0L;


/* Check each section in the heap */
for (swept = 0, pgno = 0; pgno < pgMapSize; pgno += pgcount)
{
if (pgMap[pgno] != PgBusyFirst) { pgcount = 1; continue; }

sect	= sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
pgcount = sect->pgCount;

if (sect->isFixed)
{
	got = stoGcSweepFixed(sect);
	swept += got;
}
else
	swept += stoGcSweepMixed(sect);
}

for (ix = 0; ix < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); ix++) {
fixedTail[ix]->next = 0;
fixedPieces[ix] = fixedHeadStruct[ix].next;

freeFixedPieces[ix] = freeFixedStruct[ix];
busyFixedPieces[ix] = busyFixedStruct[ix];
}
2404#ifdef USE_MEMORY_CLIMATE
finiMemoryClimateHistogram();
showMemoryClimateHistogram(stdoutstdout);
2407#endif
return swept;
2409}

2411localstatic int
2412stoGcSweepFixed(Section *sect)
2413{
int	qmcount, qmsize, qmsizeix, qmno, qmbusy, mark, swept;
QmInfo	qmtag;
char	*data;
FxMem	*pc, *nfixedTail;
ULong	nfixedFree;

data	 = (char *) sect->data;
qmcount	 = sect->qmCount;
qmsize	 = sect->qmSize;
qmsizeix = sect->qmSizeIndex;
swept	 = 0;
qmbusy	 = 0;
nfixedTail = fixedTail[qmsizeix];
nfixedFree = 0L;

for (qmno = 0; qmno < qmcount; qmno++) {
qmtag = sect->info[qmno];
mark  = QmInfoMark(qmtag)((qmtag) & 0x20);

if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBusyFirst0x80) {
	if (mark) {
		QmInfoClearMark(sect->info[qmno])((sect->info[qmno]) &= (~0x20 & 0xFF));
2436#ifdef USE_MEMORY_CLIMATE
		incrMemoryClimateHistogram(
			QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F), (int) 0, 1
		);
2440#endif
		qmbusy++;
	}
	else {
		pc = (FxMem *)(data+qmno*qmsize);
		stoPiecesGc[ QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F) ]++;
2446#ifdef USE_MEMORY_CLIMATE
		incrMemoryClimateHistogram(
			QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F), 1, 1
		);
2450#endif
		sect->info[qmno] = QmInfoMake0(QmFreeFirst)(0x40);
		fxmemCleanBody(pc, qmsize)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(FxMem),0xDD,(qmsize
) - sizeof(FxMem)) : 0);
		stoTally(stoBytesGc += qmsize)(stoBytesGc += qmsize);
		nfixedTail->next = pc;
		nfixedTail = pc;
		swept++;
	}
}
else {
	if (mark) QmInfoClearMark(sect->info[qmno])((sect->info[qmno]) &= (~0x20 & 0xFF));

2462#ifdef STO_CAN_BLACKLIST
	/* Skip blacklisted pieces */
	if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBlacklisted0xC0) {
		stoTally(stoBytesBlack += qmsize)(stoBytesBlack += qmsize);
		continue;
	}
2468#endif

	pc = (FxMem *)(data+qmno*qmsize);
	nfixedTail->next = pc;
	nfixedTail = pc;
	nfixedFree++;
}
}

if (qmbusy)
{
fixedTail[qmsizeix] = nfixedTail;
freeFixedStruct[qmsizeix] += (nfixedFree + swept);
busyFixedStruct[qmsizeix] += qmbusy;
}
else
pagesPut((Page *) sect, sect->pgCount);
return swept;
2486}

2488localstatic int
2489stoGcSweepMixed(Section *sect)
2490{
int	qmcount, qmsize, qmno, qi, nq, sz, mark, swept, qmbusy;
QmInfo	qmtag;
MxMem	*pc;
char	*data;
Pointer pstart, pend, pfront;
ULong	nMixedFree = freeMixedBytes;
ULong	nMixedBusy = busyMixedBytes;

data	= (char *) sect->data;
qmsize	= sect->qmSize;
qmcount = sect->qmCount;

swept	= 0;
qmbusy	= 0;

for (qmno = 0; qmno < qmcount; qmno += nq) {
pc    = (MxMem *)(data + qmno*qmsize);
sz    = pc->nbytesThis;
nq    = sz/sect->qmSize;
qmtag = sect->info[qmno];
mark  = QmInfoMark(qmtag)((qmtag) & 0x20);

if (!mark && QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBusyFirst0x80) {
	MxMem	*npc   = mxmemNext(pc)((pc)->isLast ? 0 : (MxMem *)((Pointer)((char *)((char *)(
pc)) + ((long)(pc)->nbytesThis))));

	/* Two cases, depending on whether might merge. */
	if (npc == 0 || !npc->isFree) {

		/* Free piece. */
		stoPiecesGc[ QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F) ]++;
2521#ifdef USE_MEMORY_CLIMATE
		incrMemoryClimateHistogram(
			QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F), 1, 1
		);
2525#endif
		sect->info[qmno]  = QmInfoMake0(QmFreeFirst)(0x40);
		mxmemCleanBody(pc, sz)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0);
		stoTally(stoBytesGc += sz-MxMemHeadSize)(stoBytesGc += sz-(sizeof(MxMem) - sizeof(MxMemU)));
		piecePutMixed(pc);
		swept++;
	}
	else {
		/* Save info, in case of merge. */
		Length nqmno	  = qmno + nq;
		ULong  nsz	  = npc->nbytesThis;
		Length nnq	  = nsz/sect->qmSize;
		QmInfo nqmtag	  = sect->info[nqmno];

		/* Free piece. */
		stoPiecesGc[ QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F) ]++;
2541#ifdef USE_MEMORY_CLIMATE
		incrMemoryClimateHistogram(
			QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F), 1, 1
		);
2545#endif
		sect->info[qmno]  = QmInfoMake0(QmFreeFirst)(0x40);
		mxmemCleanBody(pc, sz)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(MxMem),0xDD,(sz
) - sizeof(MxMem)) : 0);
		stoTally(stoBytesGc += sz-MxMemHeadSize)(stoBytesGc += sz-(sizeof(MxMem) - sizeof(MxMemU)));
		piecePutMixed(pc);
		swept++;

		/* Handle if next piece was merged. */
		if (QmInfoKind(sect->info[nqmno])((sect->info[nqmno]) & 0xC0)==QmFollow0x00) {
			if (QmInfoMark(nqmtag)((nqmtag) & 0x20)) {
				int N = nqmno+nnq;
				for (qi = nqmno; qi < N; qi++)
					QmInfoClearMark(((sect->info[qi]) &= (~0x20 & 0xFF))
					  sect->info[qi])((sect->info[qi]) &= (~0x20 & 0xFF));
			}
			nq += nnq;
		}
	}
	nMixedFree += sz;
}
else if (mark) {
2566#ifdef USE_MEMORY_CLIMATE
	incrMemoryClimateHistogram(
		QmInfoCode(sect->info[qmno])((sect->info[qmno]) & 0x1F), (int) 0, 1
	);
2570#endif
	for (qi = qmno; qi < qmno+nq; qi++)
	    QmInfoClearMark(sect->info[qi])((sect->info[qi]) &= (~0x20 & 0xFF));

	if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBusyFirst0x80)
		qmbusy += nq;
	nMixedBusy += sz;
}
}

/* Return pages if no busy pieces & sect does not contain frontier. */
pstart = ptrCanon((char *) sect)((Pointer)((char *) sect));
pend   = ptrCanon((char *) sect + sect->pgCount * PgSize)((Pointer)((char *) sect + sect->pgCount * (1L<<12))
);
pfront = ptrCanon((char *) mixedFrontier)((Pointer)((char *) mixedFrontier));

if (!qmbusy && (pfront < pstart || pend <= pfront)) {
mxmemUnlinkFromBTree((MxMem *) data, &mixedPieces){ MxMemDLL *dll = mxmemUnlink((MxMem *) data); if ((!dll->
pieces)) { btreeDeleteX((&mixedPieces), dll->nbytes, (
(void*)0), mxmemFreeBTree); mxmemFreeDLL(dll); } };
pagesPut((Page *) sect, sect->pgCount);
}
else
{
/* Note these changes in busy/free counts */
freeMixedBytes = nMixedFree;
busyMixedBytes = nMixedBusy;
}
return swept;
2596}


2599/****************************************************************************
*
* :: Audit code
*
***************************************************************************/

2605#ifndef NDEBUG

2607localstatic  void	stoAuditHeapLocation	 (void);
2608localstatic  void	stoAuditMapPages	 (void);

2610localstatic  long *	stoAuditFixedSizeSections(void);
2611localstatic  long *	stoAuditFixedSizePieces	 (void);

2613localstatic  long	stoAuditMixedSizeSections(void);
2614localstatic  long	stoAuditMixedSizePieces	 (void);

2616static long	nMixed, nSizes;

2618/*
* Main entry into the audit code.
*/
2621localstatic void
2622stoAuditAll(void)
2623{
long	i, n1, n2, *a1, *a2;

nMixed = 0, nSizes = 0;

stoAuditHeapLocation();
stoAuditMapPages();

a1 = stoAuditFixedSizeSections();
a2 = stoAuditFixedSizePieces();
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++) assert(a1[i] == a2[i])do { if (!(a1[i] == a2[i])) _do_assert(("a1[i] == a2[i]"),"store.c"
,2633); } while (0);

n1 = stoAuditMixedSizeSections();
n2 = stoAuditMixedSizePieces();

assert(n1 == n2)do { if (!(n1 == n2)) _do_assert(("n1 == n2"),"store.c",2638)
; } while (0);
2639}

2641/*
* Verify heap alignment and range.
*/
2644localstatic void
2645stoAuditHeapLocation(void)
2646{
/* Verify heap is page-aligned. */
assert(ptrToLong((Pointer) heapStart) % PgSize == 0)do { if (!(((long) ((Pointer) heapStart)) % (1L<<12) ==
 0)) _do_assert(("ptrToLong((Pointer) heapStart) % PgSize == 0"
),"store.c",2648); } while (0);
assert(ptrToLong((Pointer) heapEnd)   % PgSize == 0)do { if (!(((long) ((Pointer) heapEnd)) % (1L<<12) == 0
)) _do_assert(("ptrToLong((Pointer) heapEnd) % PgSize == 0"),
"store.c",2649); } while (0);
2650}

2652/*
* Verify the page map is self-consisteng.
*/
2655localstatic void
2656stoAuditMapPages(void)
2657{
Length	i, good, pgcount;

/* Verify page map location. */
pgcount = QUO_ROUND_UP(pgMapSize * sizeof(PgInfo), PgSize)((pgMapSize * sizeof(PgInfo)) % ((1L<<12)) ? (pgMapSize
 * sizeof(PgInfo))/((1L<<12)) + 1 : (pgMapSize * sizeof
(PgInfo))/((1L<<12)));
assert(ptrToLong((Pointer) pgMap) % PgSize == 0)do { if (!(((long) ((Pointer) pgMap)) % (1L<<12) == 0))
 _do_assert(("ptrToLong((Pointer) pgMap) % PgSize == 0"),"store.c"
,2662); } while (0);
assert(pgMapUses == pgcount)do { if (!(pgMapUses == pgcount)) _do_assert(("pgMapUses == pgcount"
),"store.c",2663); } while (0);

/* Verify map contains only good entries. */
good = 0;
for (i = 0; i < pgMapSize; i++) {
switch (pgMap[i]) {
case PgFree:  case PgBusyFirst: case PgBusyFollow:
case PgPgMap: case PgBTree:	case PgDLL:
case PgForeign:
	good++;
}
}
assert(good == pgMapSize)do { if (!(good == pgMapSize)) _do_assert(("good == pgMapSize"
),"store.c",2675); } while (0);
2676}

2678/*
* Verify the pages for sections of fixed size pieces.
*/
2681localstatic long *
2682stoAuditFixedSizeSections(void)
2683{
static long fxpCount[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];

int	pgno, pgcount, qmno, qmcount, sz, ix;
QmInfo	qmtag;
Section *sect;
char	*data;

for (ix = 0; ix < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); ix++)
fxpCount[ix] = 0;

for (pgno = 0; pgno < pgMapSize;  pgno += pgcount) {
if (pgMap[pgno] != PgBusyFirst) { pgcount = 1; continue; }

/* Get section information. */
sect	= sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
pgcount = sect->pgCount;
if (!sect->isFixed) continue;

data	= (char *) sect->data;
qmcount = sect->qmCount;
ix	= sect->qmSizeIndex;
sz	= sect->qmSize;

/* Verify section consistency. */
assert(sz == fixedSize[ix])do { if (!(sz == fixedSize[ix])) _do_assert(("sz == fixedSize[ix]"
),"store.c",2708); } while (0);
assert(ptrEQ(data + qmcount*sz, (char *)sect + pgcount * PgSize))do { if (!(( ((Pointer)((Pointer)(data + qmcount*sz)) == (Pointer
)((Pointer)((char *)sect + pgcount * (1L<<12))))))) _do_assert
(("ptrEQ(data + qmcount*sz, (char *)sect + pgcount * PgSize)"
),"store.c",2709); } while (0);
assert(pgno + pgcount <= pgMapSize)do { if (!(pgno + pgcount <= pgMapSize)) _do_assert(("pgno + pgcount <= pgMapSize"
),"store.c",2710); } while (0);

/* Verify data alignment. */
if (sz < alignof(MostAlignedType)(sizeof(struct {char a; MostAlignedType b;}) - sizeof(MostAlignedType
))) {
	assert((long) data % sz == 0)do { if (!((long) data % sz == 0)) _do_assert(("(long) data % sz == 0"
),"store.c",2714); } while (0);
}
else {
	assert((long) data % alignof(MostAlignedType) == 0)do { if (!((long) data % (sizeof(struct {char a; MostAlignedType
 b;}) - sizeof(MostAlignedType)) == 0)) _do_assert(("(long) data % alignof(MostAlignedType) == 0"
),"store.c",2717); } while (0);
	assert(sz	   % alignof(MostAlignedType) == 0)do { if (!(sz % (sizeof(struct {char a; MostAlignedType b;}) -
 sizeof(MostAlignedType)) == 0)) _do_assert(("sz % alignof(MostAlignedType) == 0"
),"store.c",2718); } while (0);
}

/* Scan data. */
for (qmno = 0; qmno < qmcount; qmno++) {
	qmtag = sect->info[qmno];
	if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmFreeFirst0x40) {
		fxmemAssertCleanBody(data + qmno*sz, sz)(stoMustWash ? memltest((UByte *)(data + qmno*sz) + sizeof(FxMem
),0xDD,(sz) - sizeof(FxMem)) : 0);
		fxpCount[ix]++;
	}
	else if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmBlacklisted0xC0)
		/* Do nothing */;
	else
		assert(QmInfoKind(qmtag) == QmBusyFirst)do { if (!(((qmtag) & 0xC0) == 0x80)) _do_assert(("QmInfoKind(qmtag) == QmBusyFirst"
),"store.c",2731); } while (0);
	assert(!QmInfoMark(qmtag))do { if (!(!((qmtag) & 0x20))) _do_assert(("!QmInfoMark(qmtag)"
),"store.c",2732); } while (0);
}
}

return fxpCount;
2737}

2739/*
* Verify the recorded fixed size pieces.
*/
2742localstatic long *
2743stoAuditFixedSizePieces(void)
2744{
static long fxpCount[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];

int	pgno, qmno, sz, ix;
PgInfo	pgtag;
QmInfo	qmtag;
Section *sect;
FxMem	*pc;
char	*data;

/* Verify pieces in free lists. */
for (ix = 0; ix < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); ix++) {
fxpCount[ix] = 0;
sz = fixedSize[ix];
for (pc = fixedPieces[ix]; pc; pc = pc->next) {
	pgno  = pgNo(pc)(((long)((char *)((char *)(pc)) - (char *)(heapStart))) >>
 12);
	pgtag = pgMap[pgno];
	sect  = sectFor(pc)(pgMap[(((long)((char *)((char *)(pc)) - (char *)(heapStart))
) >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(pc)) - (
char *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(pc));
	assert(sect != 0)do { if (!(sect != 0)) _do_assert(("sect != 0"),"store.c",2762
); } while (0);

	data  = (char *) sect->data;
2765#ifdef STO_DIVISION_BY_LOOKUP1
	/* TTT */
	qmno = (sect->qmLog) ? qmLogNo(pc, sect)(((long)((char *)((char*)(pc)) - (char *)((char*)((sect)->
data)))) >> (sect)->qmLog) : qmDivNo(pc, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(pc)) -
 (char *)((char*)((sect)->data)))))]; 
	assert(qmno == qmNo(pc, sect))do { if (!(qmno == (((long)((char *)((char*)(pc)) - (char *)(
(char*)((sect)->data))))/(sect)->qmSize))) _do_assert((
"qmno == qmNo(pc, sect)"),"store.c",2768); } while (0);
2769#else
	qmno = qmNo(pc, sect)(((long)((char *)((char*)(pc)) - (char *)((char*)((sect)->
data))))/(sect)->qmSize);
2771#endif

	qmtag = sect->info[qmno];

	/* Verify kind of page. */
	assert(0 <= pgno && pgno < pgMapSize)do { if (!(0 <= pgno && pgno < pgMapSize)) _do_assert
(("0 <= pgno && pgno < pgMapSize"),"store.c",2776
); } while (0);
	assert(pgtag == PgBusyFirst || pgtag == PgBusyFollow)do { if (!(pgtag == PgBusyFirst || pgtag == PgBusyFollow)) _do_assert
(("pgtag == PgBusyFirst || pgtag == PgBusyFollow"),"store.c",
2777); } while (0);


	/* Verify kind of section. */
	assert(sect->isFixed)do { if (!(sect->isFixed)) _do_assert(("sect->isFixed")
,"store.c",2781); } while (0);
	assert(sect->qmSize == sz && sect->qmSizeIndex == ix)do { if (!(sect->qmSize == sz && sect->qmSizeIndex
 == ix)) _do_assert(("sect->qmSize == sz && sect->qmSizeIndex == ix"
),"store.c",2782); } while (0);


	/* Verify alignment in section. */
	assert(ptrLE(data, pc))do { if (!((((Pointer)(data)) <= ((Pointer)(pc))))) _do_assert
(("ptrLE(data, pc)"),"store.c",2786); } while (0);
	assert(ptrDiff((char *) pc, data) % sz == 0)do { if (!(((long)((char *)((char *) pc) - (char *)(data))) %
 sz == 0)) _do_assert(("ptrDiff((char *) pc, data) % sz == 0"
),"store.c",2787); } while (0);
	assert(0 <= qmno && qmno < sect->qmCount)do { if (!(0 <= qmno && qmno < sect->qmCount
)) _do_assert(("0 <= qmno && qmno < sect->qmCount"
),"store.c",2788); } while (0);

	/* Verify piece is free. */
	assert(QmInfoKind(qmtag) == QmFreeFirst)do { if (!(((qmtag) & 0xC0) == 0x40)) _do_assert(("QmInfoKind(qmtag) == QmFreeFirst"
),"store.c",2791); } while (0);

	fxpCount[ix]++;
}
}
return fxpCount;
2797}

2799/*
* Verify the pages for sections of mixed size pieces.
*/
2802localstatic long
2803stoAuditMixedSizeSections(void)
2804{
int	pgno, pgcount, qmno, qmcount, qmsize, sz, nq, i, cd;
long	mxpBytes;
QmInfo	qmtag;
Section *sect;
MxMem	*pc;
char	*data;

mxpBytes = 0;

/* Verify pages with mixed size pieces. */
for (pgno = 0; pgno < pgMapSize;  pgno += pgcount) {
if (pgMap[pgno] != PgBusyFirst) { pgcount = 1; continue; }

/* Get section information. */
sect	= sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
pgcount = sect->pgCount;
if (sect->isFixed) continue;

data	= (char *) sect->data;
qmcount = sect->qmCount;
qmsize	= sect->qmSize;

/* Verify section consistency. */
assert(qmsize % MixedSizeQuantum == 0)do { if (!(qmsize % (32*sizeof(Pointer)) == 0)) _do_assert(("qmsize % MixedSizeQuantum == 0"
),"store.c",2828); } while (0);
assert(ptrEQ(ptrOff(data, qmcount*(long)qmsize),ptrOff((char *)sect, pgcount*PgSize)))do { if (!(( ((Pointer)((Pointer)(((Pointer)((char *)(data) +
 (qmcount*(long)qmsize))))) == (Pointer)((Pointer)(((Pointer)
((char *)((char *)sect) + (pgcount*(1L<<12)))))))))) _do_assert
(("ptrEQ(ptrOff(data, qmcount*(long)qmsize),ptrOff((char *)sect, pgcount*PgSize))"
),"store.c",2829); } while (0);
assert(pgno + pgcount <= pgMapSize)do { if (!(pgno + pgcount <= pgMapSize)) _do_assert(("pgno + pgcount <= pgMapSize"
),"store.c",2830); } while (0);

for (i = pgno+1; i < pgno + pgcount; i++)
	assert(pgMap[i] == PgBusyFollow)do { if (!(pgMap[i] == PgBusyFollow)) _do_assert(("pgMap[i] == PgBusyFollow"
),"store.c",2833); } while (0);

if (pgno + pgcount < pgMapSize) {
	assert(pgMap[pgno + pgcount] != PgBusyFollow)do { if (!(pgMap[pgno + pgcount] != PgBusyFollow)) _do_assert
(("pgMap[pgno + pgcount] != PgBusyFollow"),"store.c",2836); }
 while (0);
}

/* Verify data alignment. */
assert(ptrToLong(data) % alignof(MostAlignedType) == 0)do { if (!(((long) (data)) % (sizeof(struct {char a; MostAlignedType
 b;}) - sizeof(MostAlignedType)) == 0)) _do_assert(("ptrToLong(data) % alignof(MostAlignedType) == 0"
),"store.c",2840); } while (0);
assert(qmsize	       % alignof(MostAlignedType) == 0)do { if (!(qmsize % (sizeof(struct {char a; MostAlignedType b
;}) - sizeof(MostAlignedType)) == 0)) _do_assert(("qmsize % alignof(MostAlignedType) == 0"
),"store.c",2841); } while (0);

/* Scan data. */
for (qmno = 0; qmno < qmcount; qmno += nq) {
	pc	  = (MxMem *)ptrOff(data, qmno*(long)qmsize)((Pointer)((char *)(data) + (qmno*(long)qmsize)));
	sz	  = pc->nbytesThis;
	nq	  = sz/qmsize;

	/* Verify context. */
	assert(sz > 1)do { if (!(sz > 1)) _do_assert(("sz > 1"),"store.c",2850
); } while (0);			/* sz == 1 => fixed */
	assert(ptrEQ(pc->sect, sect))do { if (!(( ((Pointer)((Pointer)(pc->sect)) == (Pointer)(
(Pointer)(sect)))))) _do_assert(("ptrEQ(pc->sect, sect)"),
"store.c",2851); } while (0);

	/* Verify boundary conditions. */
	assert((pc->isFirst) == (qmno	 == 0))do { if (!((pc->isFirst) == (qmno == 0))) _do_assert(("(pc->isFirst) == (qmno == 0)"
),"store.c",2854); } while (0);
	assert((pc->isLast)  == (qmno+nq == qmcount))do { if (!((pc->isLast) == (qmno+nq == qmcount))) _do_assert
(("(pc->isLast) == (qmno+nq == qmcount)"),"store.c",2855);
 } while (0);

	/* Verify neighbours. */
	assert(qmno + nq <= qmcount)do { if (!(qmno + nq <= qmcount)) _do_assert(("qmno + nq <= qmcount"
),"store.c",2858); } while (0);
	assert(pc->nbytesThis % qmsize == 0)do { if (!(pc->nbytesThis % qmsize == 0)) _do_assert(("pc->nbytesThis % qmsize == 0"
),"store.c",2859); } while (0);
	assert(pc->nbytesPrev % qmsize == 0)do { if (!(pc->nbytesPrev % qmsize == 0)) _do_assert(("pc->nbytesPrev % qmsize == 0"
),"store.c",2860); } while (0);

	if (!pc->isFirst) {
		i = qmno - pc->nbytesPrev/qmsize;
		assert(0 <= i && i <= qmcount)do { if (!(0 <= i && i <= qmcount)) _do_assert(
("0 <= i && i <= qmcount"),"store.c",2864); } while
 (0);

		qmtag = sect->info[i];
		cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);
		assert(cd == QmFreeFirst || cd == QmBusyFirst)do { if (!(cd == 0x40 || cd == 0x80)) _do_assert(("cd == QmFreeFirst || cd == QmBusyFirst"
),"store.c",2868); } while (0);
	}
	if (!pc->isLast) {
		i = qmno + pc->nbytesThis/qmsize;
		assert(0 <= i && i <= qmcount)do { if (!(0 <= i && i <= qmcount)) _do_assert(
("0 <= i && i <= qmcount"),"store.c",2872); } while
 (0);

		qmtag = sect->info[i];
		cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);
		assert(cd == QmFreeFirst || cd == QmBusyFirst)do { if (!(cd == 0x40 || cd == 0x80)) _do_assert(("cd == QmFreeFirst || cd == QmBusyFirst"
),"store.c",2876); } while (0);
	}

	/* Verify tags. */
	qmtag = sect->info[qmno];
	cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);
	assert(!QmInfoMark(qmtag))do { if (!(!((qmtag) & 0x20))) _do_assert(("!QmInfoMark(qmtag)"
),"store.c",2882); } while (0);

	if (pc->isFree) {
		mxmemAssertCleanBody(pc, pc->nbytesThis)(stoMustWash ? memltest((UByte *)(pc) + sizeof(MxMem),0xDD,(pc
->nbytesThis) - sizeof(MxMem)) : 0);
		assert(cd == QmFreeFirst)do { if (!(cd == 0x40)) _do_assert(("cd == QmFreeFirst"),"store.c"
,2886); } while (0);
	}
	else if (ptrEQ(pc, mixedFrontier)( ((Pointer)((Pointer)(pc)) == (Pointer)((Pointer)(mixedFrontier
))))) {
		mxmemAssertCleanBody(pc, pc->nbytesThis)(stoMustWash ? memltest((UByte *)(pc) + sizeof(MxMem),0xDD,(pc
->nbytesThis) - sizeof(MxMem)) : 0);
		assert(cd == QmFreeFirst)do { if (!(cd == 0x40)) _do_assert(("cd == QmFreeFirst"),"store.c"
,2890); } while (0);
	}
	else
		assert(cd == QmBusyFirst)do { if (!(cd == 0x80)) _do_assert(("cd == QmBusyFirst"),"store.c"
,2893); } while (0);

	for (i = qmno+1; i < qmno+nq; i++) {
		qmtag = sect->info[i];
		cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);
		assert(!QmInfoMark(qmtag))do { if (!(!((qmtag) & 0x20))) _do_assert(("!QmInfoMark(qmtag)"
),"store.c",2898); } while (0);
		assert(cd == QmFollow)do { if (!(cd == 0x00)) _do_assert(("cd == QmFollow"),"store.c"
,2899); } while (0);
	}
	if (qmno+nq < qmcount) {
		qmtag = sect->info[qmno+nq];
		cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);
		assert(cd != QmFollow)do { if (!(cd != 0x00)) _do_assert(("cd != QmFollow"),"store.c"
,2904); } while (0);
	}

	if (pc->isFree) mxpBytes += sz;
}
}

return mxpBytes;
2912}

2914/*
* Verify the recorded mixed size pieces.
*/
2917localstatic long	stoAuditBTree	(BTree bt, BTreeKey *pLoBd, BTreeKey *pHiBd);
2918localstatic long	stoAuditDLL	(Length l, MxMemDLL *dll);

2920localstatic long
2921stoAuditMixedSizePieces(void)
2922{
return stoAuditBTree(mixedPieces, NULL((void*)0), NULL((void*)0));
2924}

2926localstatic long
2927stoAuditBTree(BTree bt, BTreeKey *pLoBd, BTreeKey *pHiBd)
2928{
BTreePart	xp, x0, xN;
int		isRoot = !pLoBd && !pHiBd;
int		n, pgno;
long		mxpBytes;

if (isRoot && !bt) return 0;

/* Node info. */
assert(bt != 0)do { if (!(bt != 0)) _do_assert(("bt != 0"),"store.c",2937); }
 while (0);
assert(bt->t == MixedBTreeT)do { if (!(bt->t == 16)) _do_assert(("bt->t == MixedBTreeT"
),"store.c",2938); } while (0);
n    = bt->nKeys;
x0   = bt->part;
xN   = bt->part + n;

/* Verify bt points to a node entirely within a B-tree node page. */
pgno = pgNo(bt)(((long)((char *)((char *)(bt)) - (char *)(heapStart))) >>
 12);
assert(0 <= pgno && pgno < pgMapSize)do { if (!(0 <= pgno && pgno < pgMapSize)) _do_assert
(("0 <= pgno && pgno < pgMapSize"),"store.c",2945
); } while (0);
assert(pgMap[pgno] == PgBTree)do { if (!(pgMap[pgno] == PgBTree)) _do_assert(("pgMap[pgno] == PgBTree"
),"store.c",2946); } while (0);

pgno = pgNo((char *)bt + btreeNodeSize(bt->t) - 1)(((long)((char *)((char *)((char *)bt + (sizeof(struct btree)
 + (2*(bt->t)) * sizeof(struct btreePart) - 10 * sizeof(struct
 btreePart)) - 1)) - (char *)(heapStart))) >> 12);
assert(0 <= pgno && pgno < pgMapSize)do { if (!(0 <= pgno && pgno < pgMapSize)) _do_assert
(("0 <= pgno && pgno < pgMapSize"),"store.c",2949
); } while (0);
assert(pgMap[pgno] == PgBTree)do { if (!(pgMap[pgno] == PgBTree)) _do_assert(("pgMap[pgno] == PgBTree"
),"store.c",2950); } while (0);

/* Verify bt has legal number of keys. */
assert((isRoot ? 0 : bt->t-1) <= n && n <= 2*bt->t-1)do { if (!((isRoot ? 0 : bt->t-1) <= n && n <=
 2*bt->t-1)) _do_assert(("(isRoot ? 0 : bt->t-1) <= n && n <= 2*bt->t-1"
),"store.c",2953); } while (0);

/* Verify order of keys: Note duplicate keys are not allowed here. */
if (pLoBd) { assert(*pLoBd < x0->key)do { if (!(*pLoBd < x0->key)) _do_assert(("*pLoBd < x0->key"
),"store.c",2956); } while (0); }
for (xp = x0+1; xp < xN; xp++) assert((xp-1)->key < xp->key)do { if (!((xp-1)->key < xp->key)) _do_assert(("(xp-1)->key < xp->key"
),"store.c",2957); } while (0);
if (pHiBd) { assert((xN-1)->key < *pHiBd)do { if (!((xN-1)->key < *pHiBd)) _do_assert(("(xN-1)->key < *pHiBd"
),"store.c",2958); } while (0); }

/* Check descendants. */
mxpBytes = 0;
for (xp = x0; xp < xN; xp++)
mxpBytes += stoAuditDLL((Length)xp->key,(MxMemDLL *)xp->entry);
if (!bt->isLeaf) {
mxpBytes += stoAuditBTree(x0->branch, pLoBd, &x0->key);
for (xp = x0+1; xp < xN; xp++)
	mxpBytes +=
	    stoAuditBTree(xp->branch, &(xp-1)->key, &xp->key);
mxpBytes += stoAuditBTree(xN->branch, &(xN-1)->key, pHiBd);
}
return mxpBytes;
2972}

2974localstatic long
2975stoAuditDLL(Length nbytes, MxMemDLL *dll)
2976{
int	pgno;
long	mxpBytes;
MxMem	*P0, *P, *A, *B;

nSizes++;
/* Verify dll points into DLL page. */
assert(dll != 0)do { if (!(dll != 0)) _do_assert(("dll != 0"),"store.c",2983)
; } while (0);
pgno = pgNo(dll)(((long)((char *)((char *)(dll)) - (char *)(heapStart))) >>
 12);
assert(0 <= pgno && pgno < pgMapSize)do { if (!(0 <= pgno && pgno < pgMapSize)) _do_assert
(("0 <= pgno && pgno < pgMapSize"),"store.c",2985
); } while (0);
assert(pgMap[pgno] == PgDLL)do { if (!(pgMap[pgno] == PgDLL)) _do_assert(("pgMap[pgno] == PgDLL"
),"store.c",2986); } while (0);

/* Verify node. */
assert(dll->nbytes == nbytes)do { if (!(dll->nbytes == nbytes)) _do_assert(("dll->nbytes == nbytes"
),"store.c",2989); } while (0);
assert(dll->pieces != 0)do { if (!(dll->pieces != 0)) _do_assert(("dll->pieces != 0"
),"store.c",2990); } while (0);

/* Verify center of DLL. */
P = P0 = dll->pieces;
assert(P->isFree)do { if (!(P->isFree)) _do_assert(("P->isFree"),"store.c"
,2994); } while (0);
assert(P->nbytesThis == nbytes)do { if (!(P->nbytesThis == nbytes)) _do_assert(("P->nbytesThis == nbytes"
),"store.c",2995); } while (0);
assert(P->body.free.dll == dll)do { if (!(P->body.free.dll == dll)) _do_assert(("P->body.free.dll == dll"
),"store.c",2996); } while (0);
A = P->body.free.linkA; if (A) { assert(A->body.free.linkB == P)do { if (!(A->body.free.linkB == P)) _do_assert(("A->body.free.linkB == P"
),"store.c",2997); } while (0); }
B = P->body.free.linkB; if (B) { assert(A->body.free.linkA == P)do { if (!(A->body.free.linkA == P)) _do_assert(("A->body.free.linkA == P"
),"store.c",2998); } while (0); }
mxpBytes = nbytes;
nMixed++;

/* Verify A direction of DLL. */
for (P = P0->body.free.linkA; P; P = A) {
assert(P->isFree)do { if (!(P->isFree)) _do_assert(("P->isFree"),"store.c"
,3004); } while (0);
assert(P->nbytesThis == nbytes)do { if (!(P->nbytesThis == nbytes)) _do_assert(("P->nbytesThis == nbytes"
),"store.c",3005); } while (0);
assert(P->body.free.dll == dll)do { if (!(P->body.free.dll == dll)) _do_assert(("P->body.free.dll == dll"
),"store.c",3006); } while (0);
A = P->body.free.linkA;
if (A) { assert(A->body.free.linkB == P)do { if (!(A->body.free.linkB == P)) _do_assert(("A->body.free.linkB == P"
),"store.c",3008); } while (0); }
mxpBytes += nbytes;
nMixed++;
}

/* Verify B direction of DLL. */
for (P = P0->body.free.linkB; P; P = B) {
assert(P->isFree)do { if (!(P->isFree)) _do_assert(("P->isFree"),"store.c"
,3015); } while (0);
assert(P->nbytesThis == nbytes)do { if (!(P->nbytesThis == nbytes)) _do_assert(("P->nbytesThis == nbytes"
),"store.c",3016); } while (0);
assert(P->body.free.dll == dll)do { if (!(P->body.free.dll == dll)) _do_assert(("P->body.free.dll == dll"
),"store.c",3017); } while (0);
B = P->body.free.linkB;
if (B) { assert(A->body.free.linkA == P)do { if (!(A->body.free.linkA == P)) _do_assert(("A->body.free.linkA == P"
),"store.c",3019); } while (0); }
mxpBytes += nbytes;
nMixed++;
}
return mxpBytes;
3024}

3026#endif

3028long
3029stoShowMixedSizeSections(void)
3030{
int	pgno, pgcount, qmno, qmcount, qmsize, sz, nq, i, cd;
QmInfo	qmtag;
Section *sect;
MxMem	*pc;
char	*data;
Bool	anyMarked = false((int) 0);

fprintf(osStderr, "- - - -\n");
for (pgno = 0; pgno < pgMapSize;  pgno += pgcount) {
if (pgMap[pgno] != PgBusyFirst) { pgcount = 1; continue; }

/* Get section information. */
sect	= sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
pgcount = sect->pgCount;
data	= (char *) sect->data;
qmcount = sect->qmCount;
qmsize	= sect->qmSize;

if (sect->isFixed) {
	fprintf(osStderr,"(:::Fx %d[%d:%d:%d]:::)\n",
		qmsize,pgno,pgcount,qmcount);
	continue;
}
else {
	fprintf(osStderr,"(:::Mx %d[%d:%d:%d]\n",
		qmsize,pgno,pgcount,qmcount);
}


for (qmno = 0; qmno < qmcount; qmno += nq) {
	pc	  = (MxMem *)ptrOff(data, qmno*(long)qmsize)((Pointer)((char *)(data) + (qmno*(long)qmsize)));
	sz	  = pc->nbytesThis;
	nq	  = sz/qmsize;

	if (pc->isFirst) fprintf(osStderr, "<<\n");

	if (!pc->isFirst)
		fprintf(osStderr, "(%ld)\n",
			pc->nbytesPrev/qmsize);
	fprintf(osStderr, "%p=(%d){", (void*) pc, nq);
	if (pc->isFree)
		fprintf(osStderr, "F/");
	else
		fprintf(osStderr, "B/");

	if (ptrEQ(pc, mixedFrontier)( ((Pointer)((Pointer)(pc)) == (Pointer)((Pointer)(mixedFrontier
)))))
		fprintf(osStderr, "<frontier>");

	for (i = qmno; i < qmno+nq; i++) {
		qmtag = sect->info[i];
		cd    = QmInfoKind(qmtag)((qmtag) & 0xC0);

		if (QmInfoMark(qmtag)((qmtag) & 0x20)) {
			fprintf(osStderr, "<MARK>");
			anyMarked = true1;
		}
		switch (cd) {
		case QmFreeFirst0x40:
			fprintf(osStderr, "f"); break;
		case QmBusyFirst0x80:
			fprintf(osStderr, "b"); break;
		case QmFollow0x00:
			fprintf(osStderr, "."); break;
		case QmBlacklisted0xC0:
			fprintf(osStderr, "."); break;
		default:
			fprintf(osStderr, "=[%x]", cd); break;
		}
	}
	fprintf(osStderr, "}");
	if (pc->isLast) { fprintf(osStderr, "\n>>"); }
	if (nq == 0) { fprintf(osStderr, "BUG!!\n"); exit(int0((int) 0)); }

}
fprintf(osStderr, "\n:::)\n");
}
fprintf(osStderr, "- - - -\n");
if (anyMarked) exit(int0((int) 0));
return 0;
3110}

3112/****************************************************************************
*
* :: Tuning
*
***************************************************************************/

3118/*
* Sort free lists into ascending address order.
* This does not use QmInfo so it can be used even without tags.
*/
3122localstatic void
3123stoRebuildFreeLists(void)
3124{
Section *sect;
int	ix, pgno, pgcount;
FxMem	*pc, *hd, *fp;

/* Initialize each section's free list to 0. */
for (pgno = 0; pgno < pgMapSize; pgno += pgcount) {
if (pgMap[pgno] != PgBusyFirst)
	pgcount	   = 1;
else {
	sect	   = sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
	sect->free = 0;
	pgcount	   = sect->pgCount;
}
}

/* Organize pieces from the free lists into the per-section lists. */
for (ix = 0; ix < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); ix++) {
pc = fixedPieces[ix];
fixedPieces[ix] = 0;
while (pc) {
	hd   = pc;
	pc   = pc->next;
	sect = sectFor((Pointer) hd)(pgMap[(((long)((char *)((char *)((Pointer) hd)) - (char *)(heapStart
))) >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)((Pointer
) hd)) - (char *)(heapStart))) >> 12)) * (1L<<12)
))))):_sectFor((Pointer) hd));
	hd->next = sect->free;
	sect->free = hd;
}
}
/* Join the per-lists to make the new free lists. */
for (pgno = pgMapSize-1; pgno >= 0;  pgno--) {
if (pgMap[pgno] != PgBusyFirst) continue;

sect = sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));
if (!sect->isFixed) continue;

ix   = sect->qmSizeIndex;
pc   = fixedPieces[ix];
fp   = sect->free;

while (fp) {
	hd = fp;
	fp = fp->next;
	hd->next = pc;
	pc = hd;
}
fixedPieces[ix] = pc;
}
3171}

3173/****************************************************************************
*
* :: Externally visible operations
*
***************************************************************************/


3180localstatic int
3181stoInit(void)
3182{
StoInfoObj	info;
int	i, j, sz0, sz;
gcTraceFile = 0;

3187#ifdef USE_MEMORY_CLIMATE
limitNumberOfMemoryClimates(QmCodeMask0x1F);
3189#endif

if (osGetEnv("GC_FRUGAL")) GcIsFrugal = true1;
21
←
Assuming the condition is false→
22
←
Taking false branch→

if (GcIsFrugal)
23
←
Assuming 'GcIsFrugal' is 0→
24
←
Taking false branch→
{
GcEffectiveFactorNum = GcFrugalFactorNum;
GcEffectiveFactorDen = GcFrugalFactorDen;
}

if (osGetEnv("GC_GEFN")) GcEffectiveFactorNum = atoi(osGetEnv("GC_GEFN"));
25
←
Assuming the condition is false→
26
←
Taking false branch→
if (osGetEnv("GC_GEFD")) GcEffectiveFactorDen = atoi(osGetEnv("GC_GEFD"));
27
←
Assuming the condition is false→
28
←
Taking false branch→

if (osGetEnv("GC_GGFN")) GcGrowthFactorNum = atoi(osGetEnv("GC_GGFN"));
29
←
Assuming the condition is false→
30
←
Taking false branch→
if (osGetEnv("GC_GGFD")) GcGrowthFactorDen = atoi(osGetEnv("GC_GGFD"));
31
←
Assuming the condition is false→
32
←
Taking false branch→

if (osGetEnv("GC_DETAIL")) markingStats = true1;
33
←
Assuming the condition is false→
34
←
Taking false branch→


/* Initialize memory mapper. */
osMemMap(int0((int) 0));

/* Statistics */
stoBytesOwn   = 0;
stoBytesAlloc = 0;
stoBytesFree  = 0;
stoBytesGc    = 0;
stoBytesBlack = 0;

/* Page map */
pgmapInit();

/* Heap */
heapStart = (char *) ptrOff((char *) pgMap, long0)((Pointer)((char *)((char *) pgMap) + (((long) 0))));
heapEnd	  = (char *) ptrOff((char *) pgMap, pgMapUses*PgSize)((Pointer)((char *)((char *) pgMap) + (pgMapUses*(1L<<12
))));
pgmapMod((Page *) pgMap, pgMapUses, PgPgMap);
35
←
Calling 'pgmapMod'→

/* Fixed pieces */
for (sz0 = 0, i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); sz0 = sz+1, i++) {
sz = fixedSize[i];
for (j = sz0; j <= sz; j++) {
	fixedSizeFor	 [j] = sz;
	fixedSizeIndexFor[j] = i;
}
}

/* Free lists and fixed-sized store counting */
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++) {
fixedPieces[i] = 0;
freeFixedPieces[i] = 0L;
busyFixedPieces[i] = 0L;
}


/* Mixed-sized store counting */
freeMixedBytes = 0L;
busyMixedBytes = 0L;


3248#ifdef STO_DIVISION_BY_LOOKUP1
/* Initialise division lookup-table */
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++)
{
int table = -(fixedSizeLog[i]+1);
int size  = fixedSize[i];


/* Skip sizes which don't require division */
if (fixedSizeLog[i] >= 0) continue;


/* Compute the divisions */
for (j = 0;j < PgSize(1L<<12);j++)
	stoDivTable[table][j] = j / size;
}
3264#endif


3267#ifndef FOAM_RTS
/* All objects contain pointers */
info.hasPtrs = 1;
for (i = 0;i < STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])); i++)
{
info.code = i;
stoRegister(&info);
}
3275#endif


/* Mixed pieces */
mixedPieces   = 0;
mixedFrontier = 0;
stoWatchFrontier(mixedFrontier);

/* User traceable objects */
for (i = 0;i < OB_MAX256;i++) stoObAldorTracer[i] = (StoFiClos)0;
for (i = 0;i < OB_MAX256;i++) stoObCTracer[i] = (StoTraceFun)0;

stoIsInit     =	 pgMap != 0;

gcTimer.time = 0;
gcTimer.live = 0;

return stoIsInit;
3293}


3296/*
* Added specifically for use with LIP big integers
*/
3299MostAlignedType *
3300stoCAlloc(unsigned code, ULong nbytes)
3301{
MostAlignedType *result = stoAlloc(code, nbytes);
memlset(result, 0x00, nbytes);
return result;
3305}


3308MostAlignedType *
3309stoAlloc(unsigned code, ULong nbytes)
3310{
Pointer 	p;
Section 	*sect;
Length		qi;
MostAlignedType *ap;

if (!stoIsInit && !stoInit())
19
←
Assuming 'stoIsInit' is 0→
20
←
Calling 'stoInit'→
return (*stoError)(StoErr_CantBuild3);

3319#ifdef USE_MEMORY_CLIMATE
code = getMemoryClimate();
3321#endif
if (nbytes > 100*1024*1024) {
bug("stoAlloc: Too large");
}
if (nbytes==0) return NULL((void*)0); /* TTT */
if (nbytes <= FixedSizeMax(32*sizeof(Pointer)))
{
FxMem		*pc;
int		si;

si = fixedSizeIndexFor[nbytes];
pc = fixedPieces[si];

if (!pc) {
	pc = piecesGetFixed(nbytes);
	if (!pc) return (*stoError)(StoErr_OutOfMemory1);
}

fixedPieces[si] = pc->next;
p = (Pointer)pc;

if (stoMustTag)
{
	/* This is much more efficient than sectFor() */
	sect = sectOf(p)((Section *)(((Pointer)((char *)(heapStart) + ((((long)((char
 *)(p) - (char *)(heapStart))) & ~((1L<<12)-1))))))
);


3348#ifdef STO_DIVISION_BY_LOOKUP1
	/* Compute the quantum index */
	qi = (sect->qmLog) ?  qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog) : /* TTT */ 
	  /* Use division-by-lookup-table */ qmDivNo(p, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(p)) -
 (char *)((char*)((sect)->data)))))];

	assert(qi == qmNo(p, sect))do { if (!(qi == (((long)((char *)((char*)(p)) - (char *)((char
*)((sect)->data))))/(sect)->qmSize))) _do_assert(("qi == qmNo(p, sect)"
),"store.c",3353); } while (0);

3355#else
	/* Compute the quantum index */
	if (sect->qmLog)
		qi = qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog);
	else
		qi = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
3361#endif


	/* Update the info for this quantum */
	sect->info[qi] = QmInfoMake(QmBusyFirst, code)(((0x80) & 0xC0) | ((code) & 0x1F));
}

stoTally(stoBytesAlloc += fixedSize[si])(stoBytesAlloc += fixedSize[si]);
newFill (p,               fixedSize[si])(stoMustWash ? memlset (p,0xAA,fixedSize[si]) : 0);
}
else
{
MxMem		*pc;
ULong		nb;

3376#ifdef STO_LONGJMP
if (setjmp(stoAllocInner_ErrorCatch)_setjmp (stoAllocInner_ErrorCatch)) {
	p = ptrCanon(stoAllocInner_ErrorValue)((Pointer)(stoAllocInner_ErrorValue));
	return (MostAlignedType *) p;
}
3381#endif
nb = ROUND_UP(nbytes + MxMemHeadSize, MixedSizeQuantum)((nbytes + (sizeof(MxMem) - sizeof(MxMemU))) % ((32*sizeof(Pointer
))) ? (nbytes + (sizeof(MxMem) - sizeof(MxMemU))) + ((32*sizeof
(Pointer))) - (nbytes + (sizeof(MxMem) - sizeof(MxMemU))) % (
(32*sizeof(Pointer))) : (nbytes + (sizeof(MxMem) - sizeof(MxMemU
))));
pc = pieceGetMixed(nb);

if (!pc) return (*stoError)(StoErr_OutOfMemory1);

p  = (Pointer) (&pc->body.busy.data);

if (stoMustTag) {
	sect = sectFor((Pointer) pc)(pgMap[(((long)((char *)((char *)((Pointer) pc)) - (char *)(heapStart
))) >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)((Pointer
) pc)) - (char *)(heapStart))) >> 12)) * (1L<<12)
))))):_sectFor((Pointer) pc));
	qi   = qmNo(pc, sect)(((long)((char *)((char*)(pc)) - (char *)((char*)((sect)->
data))))/(sect)->qmSize);
	sect->info[qi] = QmInfoMake(QmBusyFirst, code)(((0x80) & 0xC0) | ((code) & 0x1F));
}

stoTally(stoBytesAlloc += pc->nbytesThis - MxMemHeadSize)(stoBytesAlloc += pc->nbytesThis - (sizeof(MxMem) - sizeof
(MxMemU)));
newFill (p,               pc->nbytesThis - MxMemHeadSize)(stoMustWash ? memlset (p,0xAA,pc->nbytesThis - (sizeof(MxMem
) - sizeof(MxMemU))) : 0);
}


/* Canonicalise the pointer and return it */
ap = (MostAlignedType *) ptrCanon(p)((Pointer)(p));
stoWatchAlloc(ap, nbytes);
return ap;
3404}


3407void
3408stoFree(Pointer p)
3409{
int	si;
Length	qi;
Section *sect;

if (p==0) return; /* TTT */
if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0) {
(*stoError)(StoErr_FreeBad4);
return;
}
stoWatchFree(p);

if (sect->isFixed) {
FxMem	*pc = (FxMem *) p;
si		= sect->qmSizeIndex;
if (stoMustTag) {
3425#ifdef STO_DIVISION_BY_LOOKUP1
        qi = (sect->qmLog) ? qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog) :  qmDivNo(p, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(p)) -
 (char *)((char*)((sect)->data)))))]; /* TTT */
	assert(qi == qmNo(p, sect))do { if (!(qi == (((long)((char *)((char*)(p)) - (char *)((char
*)((sect)->data))))/(sect)->qmSize))) _do_assert(("qi == qmNo(p, sect)"
),"store.c",3427); } while (0);
3428#else
	if (sect->qmLog)
		qi = qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog);
	else
		qi = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
3433#endif
	if (QmInfoKind(sect->info[qi])((sect->info[qi]) & 0xC0) != QmBusyFirst0x80)
		(*stoError)(StoErr_FreeBad4);
	sect->info[qi] = QmInfoMake0(QmFreeFirst)(0x40);
}
stoTally(stoBytesFree += fixedSize[si])(stoBytesFree += fixedSize[si]);
fxmemCleanBody(pc, fixedSize[si])(stoMustWash ? memlset ((UByte *)(pc) + sizeof(FxMem),0xDD,(fixedSize
[si]) - sizeof(FxMem)) : 0);
pc->next	= fixedPieces[si];
fixedPieces[si] = pc;
}
else {
MxMem	*pc = (MxMem *) ptrOff((char *) p, -(long)MxMemHeadSize)((Pointer)((char *)((char *) p) + (-(long)(sizeof(MxMem) - sizeof
(MxMemU)))));
3445#ifdef STO_LONGJMP
if (setjmp(stoAllocInner_ErrorCatch)_setjmp (stoAllocInner_ErrorCatch))
	return;
3448#endif
if (stoMustTag) {
	qi   = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
	if (QmInfoKind(sect->info[qi])((sect->info[qi]) & 0xC0) != QmBusyFirst0x80)
		(*stoError)(StoErr_FreeBad4);
	sect->info[qi] = QmInfoMake0(QmFreeFirst)(0x40);
}
stoTally(stoBytesFree += pc->nbytesThis - MxMemHeadSize)(stoBytesFree += pc->nbytesThis - (sizeof(MxMem) - sizeof(
MxMemU)));
mxmemCleanBody(pc, pc->nbytesThis)(stoMustWash ? memlset ((UByte *)(pc) + sizeof(MxMem),0xDD,(pc
->nbytesThis) - sizeof(MxMem)) : 0);
piecePutMixed(pc);
}
3459}

3461/*
* Return the actual size of the piece pointed to.
*/
3464ULong
3465stoSize(Pointer p)
3466{
Section *sect;

if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0) {
(*stoError)(StoErr_UsedNonalloc2);
return 0;
}
if (sect->isFixed)
return sect->qmSize;
else {
MxMem *pc = (MxMem *) ((char *) p - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU)));
return pc->nbytesThis - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU));
}
3479}

3481unsigned
3482stoCode(Pointer p)
3483{
if (stoMustTag) {
Length	qi;
Section *sect;

if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0)
	return 0;
qi = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
if (QmInfoKind(sect->info[qi])((sect->info[qi]) & 0xC0) == QmBusyFirst0x80)
	return QmInfoCode(sect->info[qi])((sect->info[qi]) & 0x1F);
}
return 0;
3495}


3498MostAlignedType *
3499stoRecode(Pointer p, unsigned code)
3500{
if (stoMustTag) {
Section *sect;
Length	qi;

if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0)
	return (*stoError)(StoErr_UsedNonalloc2);

qi = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
QmInfoSetCode(sect->info[qi], code)((sect->info[qi]) = ((sect->info[qi]) & (~0x1F &
 0xFF)) | ((code) & 0x1F));
}
return (MostAlignedType *) p;
3512}


3515MostAlignedType *
3516stoResize(Pointer p, ULong nbytes)
3517{
Section *sect;
Pointer np;
int	oc = 0;
ULong	nsz, osz;

if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0)
1
Assuming 'stoIsInit' is not equal to 0→
2
←
Assuming 'heapStart' is <= 'p'→
3
←
Assuming 'p' is < 'heapEnd'→
4
←
Assuming the condition is false→
5
←
'?' condition is false→
6
←
Assuming the condition is false→
7
←
Taking false branch→
return (*stoError)(StoErr_UsedNonalloc2);

/* true size of old piece */
if (sect->isFixed)
8
←
Assuming field 'isFixed' is 0→
9
←
Taking false branch→
osz = sect->qmSize;
else {
MxMem *pc = (MxMem *) ((char *) p - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU)));
osz = pc->nbytesThis - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU));
}

/* true size of new piece */
if (nbytes <= FixedSizeMax(32*sizeof(Pointer)))
10
←
Assuming the condition is false→
nsz = fixedSizeFor[nbytes];
else {
nsz  = ROUND_UP(nbytes + MxMemHeadSize, MixedSizeQuantum)((nbytes + (sizeof(MxMem) - sizeof(MxMemU))) % ((32*sizeof(Pointer
))) ? (nbytes + (sizeof(MxMem) - sizeof(MxMemU))) + ((32*sizeof
(Pointer))) - (nbytes + (sizeof(MxMem) - sizeof(MxMemU))) % (
(32*sizeof(Pointer))) : (nbytes + (sizeof(MxMem) - sizeof(MxMemU
))));
11
←
Taking false branch→
12
←
Assuming the condition is false→
13
←
'?' condition is false→
nsz -= MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU));
}

if (osz == nsz) return (MostAlignedType *) ptrCanon(p)((Pointer)(p));
14
←
Assuming 'osz' is not equal to 'nsz'→
15
←
Taking false branch→
if (stoMustTag) oc = QmInfoCode(sect->info[qmNo(p, sect)])((sect->info[(((long)((char *)((char*)(p)) - (char *)((char
*)((sect)->data))))/(sect)->qmSize)]) & 0x1F);
16
←
Assuming 'stoMustTag' is 0→
17
←
Taking false branch→
np = (Pointer) stoAlloc(oc, nbytes);
18
←
Calling 'stoAlloc'→
memcpy(np, p, MIN(nbytes, osz)((nbytes) < (osz) ? (nbytes) : (osz)));
stoFree(p);

return (MostAlignedType *) ptrCanon(np)((Pointer)(np));
3549}

3551int
3552stoIsPointer(Pointer p)
3553{
if (stoMustTag) {
Section *sect;
Length	qi;

if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd)))) || (sect = sectFor(p)(pgMap[(((long)((char *)((char *)(p)) - (char *)(heapStart)))
 >> 12)]==PgBusyFirst ? ((Section *) ((Page *)((Pointer
)((char *)(heapStart) + (((((long)((char *)((char *)(p)) - (char
 *)(heapStart))) >> 12)) * (1L<<12)))))):_sectFor
(p))) == 0)
	return 0;
qi = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
return QmInfoKind(sect->info[qi])((sect->info[qi]) & 0xC0) == QmBusyFirst0x80;
}
else {
if (!stoIsInit || !isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd))))) return 0;
return 1;
}
3567}

3569#define STO_SHOW_PAGES0x00000001		0x00000001
3570#define STO_SHOW_MEMORY0x00000002		0x00000002
3571#define STO_SHOW_OVERHEAD0x00000004	0x00000004
3572#define STO_SHOW_RESERVED0x00000008	0x00000008
3573#define STO_SHOW_FIXED0x00000010		0x00000010
3574#define STO_SHOW_MIXED0x00000020		0x00000020
3575#define STO_SHOW_PAGEMAP0x00000040	0x00000040
3576#define STO_SHOW_PAGEKEY0x00000080	0x00000080
3577#define STO_SHOW_MEMMAP0x00000100		0x00000100
3578#define STO_SHOW_SHOW0x00000200		0x00000200
3579#define STO_SHOW_CENSUS0x00000400		0x00000400
3580#define STO_SHOW_USAGE0x00000800		0x00000800
3581#define STO_SHOW_ALL((-1) & ~0x00000080 & ~0x00000200)		((-1) & ~STO_SHOW_PAGEKEY0x00000080 & ~STO_SHOW_SHOW0x00000200)
3582#define STO_SHOW_BEFORE_MASK(~(0x00000400 | 0x00000800))	(~(STO_SHOW_CENSUS0x00000400 | STO_SHOW_USAGE0x00000800))

3584int
3585stoShowArgs(char *detail)
3586{
int r = 0x00;


/* NULL argument means no details */
if (!detail) return 0;


/* Treat the argument as a list of words */
while (*detail)
{
char *w;
int l;

/* Skip any leading whitespace or commas */
while (*detail && (isspace(*detail)((*__ctype_b_loc ())[(int) ((*detail))] & (unsigned short
 int) _ISspace) || (*detail == ',')))
	detail++;


/* Note the starting position of the word */
if (*detail)	w = detail;
else		break; /* At EOS - stop */


/* Locate the end of the word */
while (*detail && !isspace(*detail)((*__ctype_b_loc ())[(int) ((*detail))] & (unsigned short
 int) _ISspace) && (*detail != ','))
	detail++;


/* How long is the word? */
l = detail - w;

/* Do we recognise it? */
if      (!strncmp(w,"pages",l))    r |= STO_SHOW_PAGES0x00000001;
else if (!strncmp(w,"memory",l))   r |= STO_SHOW_MEMORY0x00000002;
else if (!strncmp(w,"overhead",l)) r |= STO_SHOW_OVERHEAD0x00000004;
else if (!strncmp(w,"reserved",l)) r |= STO_SHOW_RESERVED0x00000008;
else if (!strncmp(w,"fixed",l))    r |= STO_SHOW_FIXED0x00000010;
else if (!strncmp(w,"mixed",l))    r |= STO_SHOW_MIXED0x00000020;
else if (!strncmp(w,"pagemap",l))  r |= STO_SHOW_PAGEMAP0x00000040;
else if (!strncmp(w,"pagekey",l))  r |= STO_SHOW_PAGEKEY0x00000080;
else if (!strncmp(w,"memmap",l))   r |= STO_SHOW_MEMMAP0x00000100;
else if (!strncmp(w,"census",l))   r |= STO_SHOW_CENSUS0x00000400;
else if (!strncmp(w,"usage",l))    r |= STO_SHOW_USAGE0x00000800;
else if (!strncmp(w,"all",l))      r |= STO_SHOW_ALL((-1) & ~0x00000080 & ~0x00000200);
else if (!strncmp(w,"show",l))
{
	(void)fprintf(osStderr,
"\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n%s\n\n",
"Possible values are a space or comma separated list of:",
"        all: select all options (except pagekey and show)",
"     census: display object counts/sizes by type",
"      fixed: classification and count of free fixed-size pages",
"     memmap: display the stack, heap, idata and ddata limits",
"     memory: amount of store allocated, owned etc",
"      mixed: classification and count of free mixed-size pages",
"   overhead: memory overhead of the storage manager",
"    pagekey: display the symbols used in the pagemap display",
"    pagemap: tabular display of the page map (see also pagekey)",
"      pages: classification and count of store pages",
"   reserved: amount of free memory in reserve",
"       show: display this message",
"      usage: fixed-sized pages free/busy usage");
}
}
fflush(osStderr);


/* Return the flags */
return r;
3656}


3659void
3660stoGc(void)
3661{
static int doShow = -1;

if (doShow == -1)
doShow = stoShowArgs(osGetEnv("GC_DETAIL"));
if (stoMustTag) {
static Bool inGc = false((int) 0);
if (inGc) return;
tmStart(stoGcTimer());
if (DEBUG(sto)((int) 0)) {
	if (doShow) {
		/* Census taking is special */
		if (doShow & STO_SHOW_CENSUS0x00000400)
			stoTakeCensus(1);


		/* Some things not shown before GC */
		stoShowDetail(doShow & STO_SHOW_BEFORE_MASK(~(0x00000400 | 0x00000800)));
	}
}
inGc = true1;
stoGcMarkAndSweep();
inGc = false((int) 0);
if (DEBUG(sto)((int) 0)) {
	if (doShow) {
		/* Census taking is special */
		if (doShow & STO_SHOW_CENSUS0x00000400)
			stoTakeCensus((AInt)0);


		/* Allowed to show census this time */
		stoShowDetail(doShow);
	}
}
tmStop(stoGcTimer());
}
3697}

3699void
3700stoTune(void)
3701{
stoRebuildFreeLists();
3703}

3705void
3706stoShow(void)
3707{
stoShowDetail(STO_SHOW_ALL((-1) & ~0x00000080 & ~0x00000200));
3709}


3712localstatic ULong
3713stoTakeFixedCensus(Section *sect, ULong *hist, ULong *mem)
3714{
Length	i;
ULong	nobjs = 0;
ULong	size = sect->qmSize;
int	info;


/* Count all the objects in this section */
for (i = 0; i < sect->qmCount; i++)
{
/* Skip irrevelent quanta */
if (QmInfoKind(sect->info[i])((sect->info[i]) & 0xC0) != QmBusyFirst0x80)
	continue;


/* Remember the object type */
info = QmInfoCode(sect->info[i])((sect->info[i]) & 0x1F);


/* Increment census slot for this type */
hist[info]++;


/* Increase storage count */
mem[info] += size;


/* Found another object */
nobjs++;
}


/* Return the number of objects counted. */
return nobjs;
3748}


3751localstatic ULong
3752stoTakeMixedCensus(Section *sect, ULong *hist, ULong *mem)
3753{
Length	i;
ULong	nobjs = 0;
ULong	size;
int	kind;
int	info;
MxMem	*pc;


/* Count all the objects in this section */
for (i = 0; i < sect->qmCount; i++)
{
/* Get the type of quanta */
kind = QmInfoKind(sect->info[i])((sect->info[i]) & 0xC0);


/* Skip irrevelent quanta */
if (kind != QmBusyFirst0x80)
	continue;


/* Compute the address of the piece */
pc = (MxMem *)ptrOff((char *)sect->data, i*sect->qmSize)((Pointer)((char *)((char *)sect->data) + (i*sect->qmSize
)));


/* Read the size of the data (may cover several quanta) */
size = pc->nbytesThis;


/* Remember the object type */
info = QmInfoCode(sect->info[i])((sect->info[i]) & 0x1F);


/* Increment census slot for this type */
hist[info]++;


/* Increase storage count */
mem[info] += size;


/* Found another object */
nobjs++;
}


/* Return the number of objects counted. */
return nobjs;
3801}


3804/*
* This function can be used to display a table of information about
* different types of objects which are present in the store. The
* number of objects before and after garbage collection is computed
* along with the amount of memory they use.
*/
3810void
3811stoTakeCensus(AInt before)
3812{
Length	i;
ULong	nobjs = 0L;
ULong	*hist, *mem;


/* Which table are we filling? */
hist = before ? censusBefore : censusAfter;
mem  = before ? censusMemBefore : censusMemAfter;


/* Reset the histograms */
for (i = 0;i < STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])); i++)
hist[i] = mem[i] = 0L;


/* Scan the heap counting number and size of objects */
for (i = 0; i < pgMapSize; i++)
{
if (pgMap[i] == PgBusyFirst)
{
	Section *sect = sectAt(i)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((i) *
 (1L<<12))))));


	/* Census depends on section type */
	if (sect->isFixed)
		nobjs += stoTakeFixedCensus(sect, hist, mem);
	else
		nobjs += stoTakeMixedCensus(sect, hist, mem);
}
}


/* Record the total number of objects found */
hist[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])) - 1] = nobjs;
3847}

3849static String stoCensusDivider = "---------------------------------------------------------------------------------";

3851static String stoCensusBlank = "                                                                                 ";

3853localstatic void
3854stoShowCensusBar(int hires)
3855{
String	line = stoCensusDivider;
String	blank = stoCensusBlank;


/* Decide what sort of bar to draw */
if (hires)
{
/* Field name */
(void)fprintf(osStderr, "+-");
(void)fprintf(osStderr, "%10.10s-+-", line);


/* Object counts: total, live and swept */
(void)fprintf(osStderr, "%9.9s-+-", line);
(void)fprintf(osStderr, "%9.9s-+-", line);
(void)fprintf(osStderr, "%9.9s-+-", line);


/* Object sizes: total, live and swept */
(void)fprintf(osStderr, "%6.6s-+-", line);
(void)fprintf(osStderr, "%6.6s-+-", line);
(void)fprintf(osStderr, "%6.6s-+", line);
}
else
{
/* Field name */
(void)fprintf(osStderr, "  ");
(void)fprintf(osStderr, "%10.10s +-", blank);


/* Object counts: total, live and swept */
(void)fprintf(osStderr, "%33.33s-+-", line);


/* Object sizes: total, live and swept */
(void)fprintf(osStderr, "%23.23s--+", line);
}


/* Finish the line */
(void)fprintf(osStderr, "\n");
3897}


3900localstatic void
3901stoShowCensusTitle(void)
3902{
/* Start the title */
stoShowCensusBar(int0((int) 0));


/* Field name */
(void)fprintf(osStderr, "  ");
(void)fprintf(osStderr, "%-10.10s | ", "");


/* Object counts: total, live and swept */
(void)fprintf(osStderr, "%-32.32s  | ", "        Number of objects");


/* Object sizes: total, live and swept */
(void)fprintf(osStderr, "%-23.23s  |", "      Memory used (K)");


/* Finish the line */
(void)fprintf(osStderr, "\n");


/* Start the title */
stoShowCensusBar(1);


/* Field name */
(void)fprintf(osStderr, "| ");
(void)fprintf(osStderr, "%-10.10s | ", "  Type");


/* Object counts: total, live and swept */
(void)fprintf(osStderr, "%-9.9s | ", "   Total");
(void)fprintf(osStderr, "%-9.9s | ", "    Live");
(void)fprintf(osStderr, "%-9.9s | ", "   Swept");


/* Object sizes: total, live and swept */
(void)fprintf(osStderr, "%-6.6s | ", " Total");
(void)fprintf(osStderr, "%-6.6s | ", "  Live");
(void)fprintf(osStderr, "%-6.6s |",  " Swept");


/* Finish the line */
(void)fprintf(osStderr, "\n");
stoShowCensusBar(1);
3948}


3951localstatic void
3952stoShowCensus(AInt width)
3953{
Length	i;
ULong	tmem = 0L;
ULong	lmem = 0L;


/* Compute the total store usages */
for (i = 0;(i < STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])) - 1); i++)
{
tmem += censusMemBefore[i];
lmem += censusMemAfter[i];
}


/* Shove it in the total slot */
censusMemBefore[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])) - 1] = tmem;
censusMemAfter[STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])) - 1] = lmem;


/* Display a nice title bar */
stoShowCensusTitle();


/* Now show the bars of the histogram with titles */
for (i = 0;i < STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])); i++)
{
ULong	tsize = censusMemBefore[i] / 1024;
ULong	lsize = censusMemAfter[i] / 1024;
ULong	tobjs = censusBefore[i];
ULong	lobjs = censusAfter[i];
int	last = (i == (STO_CENSUS_LIMIT(sizeof(censusName)/sizeof(censusName[0])) - 1));


/* The last line shows the totals */
if (last) stoShowCensusBar(1);


/* Field name */
(void)fprintf(osStderr, "| ");
(void)fprintf(osStderr, "%10.10s | ", censusName[i]);


/* Object counts: total, live and swept */
(void)fprintf(osStderr, "%9ld | ", tobjs);
(void)fprintf(osStderr, "%9ld | ", lobjs);
(void)fprintf(osStderr, "%9ld | ", tobjs - lobjs);


/* Object sizes: total, live and swept */
(void)fprintf(osStderr, "%6ld | ", tsize);
(void)fprintf(osStderr, "%6ld | ", lsize);
(void)fprintf(osStderr, "%6ld |", tsize - lsize);


/* Finish the row */
(void)fprintf(osStderr, "\n");
}


/* Finish with the bottom line */
stoShowCensusBar(1);
(void)fprintf(osStderr, "\n\n");
4015}


4018void
4019stoShowDetail(int stoDetail)
4020{
struct osMemMap **mm;
Length	i;
ULong	npgBusy=0, npgFree=0, npgStoMan=0, npgForeign=0, npgOther=0;
ULong	pgOHead, pcOHead, avPc;
ULong	frN[FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0]))];
String	sep = stoCensusDivider;


/*
* If we are showing some output other than the census
* then we provide a simple separator to help the user.
*/
if (stoDetail & ~STO_SHOW_CENSUS0x00000400)
(void)fprintf(osStderr, "+%76.76s\n", sep);


/* Classify and count the number of pages in the store */
for (i = 0; i < pgMapSize; i++)
{
switch (pgMap[i])
{
   case PgBusyFirst:	/* Fall through */
   case PgBusyFollow:	npgBusy++;    break;
   case PgFree:		npgFree++;    break;
   case PgPgMap:	/* Fall through */
   case PgBTree:	/* Fall through */
   case PgDLL:		npgStoMan++;  break;
   case PgForeign:	npgForeign++; break;
   default:		npgOther++;   break;
}
}


/* Show the number of different pages in the store */
if (stoDetail & STO_SHOW_PAGES0x00000001)
{
fprintf(osStderr, "| %-11s %ld: %ld busy, %ld free, ",
	"Pages:", (long) pgMapSize, (long) npgBusy, (long) npgFree);
fprintf(osStderr, "%ld overhead, %ld foreign, %ld other\n",
	npgStoMan, npgForeign, npgOther);
}


/* Show how much store has been allocated/freed/owned */
if (stoDetail & STO_SHOW_MEMORY0x00000002)
{
fprintf(osStderr, "| %-11s %ld alloc, %ld freed, %ld owned, ",
	"KBytes:",
	(stoBytesAlloc + 512)/1024,
	(stoBytesFree + 512)/1024,
	(stoBytesOwn + 512)/1024);
fprintf(osStderr, "%ld blacklisted",
	(stoBytesBlack + 512)/1024);
fprintf(osStderr, "\n");
}


/* Compute the overheads imposed by the storage manager */
pgOHead	  = pgMapSize * SectionHeadSize(sizeof(Section) + (0) * sizeof(QmInfo) - 10 * sizeof(QmInfo)
)
  + npgStoMan * PgSize(1L<<12);
pcOHead	  = 0;
for (i = 0; i < pgMapSize; i++)
if (pgMap[i] == PgBusyFirst) {
	Section *sect = sectAt(i)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((i) *
 (1L<<12))))));
	pcOHead += sect->qmCount * sizeof(QmInfo);
}


/* Show how much overhead the storage manager is using */
if (stoDetail & STO_SHOW_OVERHEAD0x00000004)
{
fprintf(osStderr, "| %-11s (%ld pg bytes + %ld pc bytes)/",
	"Overhead:", pgOHead, pcOHead);
fprintf(osStderr, "%ld owned => %d%%\n",
	stoBytesOwn,
	(int)((100*pgOHead + 100*pcOHead)/stoBytesOwn));
}


/* How much storage is being held in reserve? */
avPc = 0;
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++) {
FxMem	*pc;
Length	sz = fixedSize[i];
frN[i] = 0;
for (pc = fixedPieces[i]; pc; pc = pc->next) {
	frN[i] ++;
	avPc   += sz;
}
}


/* Show the amount of store in reserve */
if (stoDetail & STO_SHOW_RESERVED0x00000008)
{
fprintf(osStderr, "| %-11s %ld in raw pgs, ",
	"Reserve:", npgFree * PgSize(1L<<12));
fprintf(osStderr, "%ld in free lists (equiv %ld pgs)\n",
	avPc, QUO_ROUND_UP(avPc, PgSize)((avPc) % ((1L<<12)) ? (avPc)/((1L<<12)) + 1 : (avPc
)/((1L<<12))));
}


/* Show the details of fixed-size pages */
if (stoDetail & STO_SHOW_FIXED0x00000010)
{
int	wrote = 0;

fprintf(osStderr, "| %-11s %d\n", "FixedSizes:", (int) FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])));
fprintf(osStderr, "| Fixed-size free pieces:\n");
wrote = fprintf(osStderr, "|  ");
for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++)
{
	if (frN[i])
	{
		wrote += fprintf(osStderr, " %ldx%d",
				frN[i], (int) fixedSize[i]);
		if (wrote > 70)
		{
			/* Wrap long lines */
			(void)fprintf(osStderr, "\n");
			wrote = fprintf(osStderr, "|  ");
		}
	}
}
fprintf(osStderr, "\n");
}


/* Show the usage counts for fixed-size pages */
if (stoDetail & STO_SHOW_USAGE0x00000800)
{
ULong	tot;
ULong	spareMixedBytes, availMixedBytes, totalMixedBytes;
ULong	nMixedFreeK, nMixedBusyK, nMixedSpareK;
double	gceff, gcnum, gcden;
double	headroom;


/* Total number of pages under our control */
tot = npgBusy + npgFree + npgStoMan + npgOther;


/* How much headroom do we have? */
if (tot > 0)
	headroom = (double)npgFree/(double)tot;
else
	headroom = 1.0;


/* How much headroom do we need? */
gcnum = (double)GcEffectiveFactorNum;
gcden = (double)GcEffectiveFactorDen;
gceff = gcnum / gcden;


/* Neatly tabulate the results */
(void)fprintf(osStderr, "| %-11s %.1f%% (%s = %.1f%%, %s)\n",
	"Headroom:", 100.0*headroom, "gcEff", 100.0*gceff,
	(headroom < gceff) ? "too low" : "okay");
(void)fprintf(osStderr, "| Fixed-size page usage:\n");
(void)fprintf(osStderr, "|      ");
(void)fprintf(osStderr, "%4s: ", "Size");
(void)fprintf(osStderr, "%8s ", "Free");
(void)fprintf(osStderr, "%8s ", "Busy");
(void)fprintf(osStderr, "%8s ", "Spare");
(void)fprintf(osStderr, "%7s",  "HeadRm");
(void)fprintf(osStderr, "\n");

for (i = 0; i < FixedSizeCount(sizeof(fixedSize)/sizeof(fixedSize[0])); i++)
{
	ULong fxFree  = freeFixedPieces[i];
	ULong fxBusy  = busyFixedPieces[i];
	ULong fxPer   = sectQmCount(1L, fixedSize[i]);
	ULong fxSpare = fxPer*npgFree;
	ULong fxAvail = fxFree + fxSpare;
	ULong fxTotal = fxBusy + fxAvail;
	double	headrm;

	if (fxTotal > 0)
		headrm = (double)fxAvail/(double)fxTotal;
	else
		headrm = 1.0;

	(void)fprintf(osStderr, "|      ");
	(void)fprintf(osStderr, "%4ld: ", (long) fixedSize[i]);
	(void)fprintf(osStderr, "%8lu ", fxFree);
	(void)fprintf(osStderr, "%8lu ", fxBusy);
	(void)fprintf(osStderr, "%8lu ", fxSpare);
	(void)fprintf(osStderr, "%6.1f%%", 100.0*headrm);
	(void)fprintf(osStderr, "\n");
}


/* Compute mixed-size usage */
spareMixedBytes = npgFree*(PgSize(1L<<12) - MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU)));
availMixedBytes = freeMixedBytes + spareMixedBytes;
totalMixedBytes = availMixedBytes + busyMixedBytes;


/* Convert bytes into K for readability */
nMixedFreeK  = freeMixedBytes / 1024;
nMixedBusyK  = busyMixedBytes / 1024;
nMixedSpareK = spareMixedBytes / 1024;


/* Compute headroom */
if (totalMixedBytes > 0)
{
	double num = (double)availMixedBytes;
	double den = (double)totalMixedBytes;
	headroom = num/den;
}
else
	headroom = 1.0;


/* Show mixed-size usage. */
(void)fprintf(osStderr, "| Mixed-size page usage: ");
(void)fprintf(osStderr, "%luK free, ", nMixedFreeK);
(void)fprintf(osStderr, "%luK busy, ", nMixedBusyK);
(void)fprintf(osStderr, "%luK spare, ", nMixedSpareK);
(void)fprintf(osStderr, "%.1f%% headroom\n", 100.0*headroom);
}


/* Show details about mixed-size pages */
if (stoDetail & STO_SHOW_MIXED0x00000020)
{
fprintf(osStderr, "| Mixed-size free pieces:\n|  ");
btreeNMap((BTreeEltFun) mxmemShow, mixedPieces);
putc('\n',osStderr);
}


/* Display the whole store at page resolution */
if (stoDetail & STO_SHOW_PAGEMAP0x00000040)
{
fprintf(osStderr, "| %-11s [%ld pages]:",
	"Page map:", (long) pgMapSize);
for (i = 0; i < pgMapSize; i++)
{
	if (i % 64 == 0)
	{
		fprintf(osStderr, "\n|%5ld-%5ldK ",
			(i) * PgSize(1L<<12)/1024,
			(i+63) * PgSize(1L<<12)/1024);
	}

	switch (pgMap[i])
	{
	   case PgFree:		putc('+',osStderr); break;
	   case PgBusyFirst:
	   {
		Section *sect = sectAt(i)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((i) *
 (1L<<12))))));

		if (!sect->isFixed)
			putc('m',osStderr);
		else if (sect->qmSizeIndex < 10)
			putc('0' + sect->qmSizeIndex,osStderr);
		else if (sect->qmSizeIndex < 16)
			putc('a' + sect->qmSizeIndex - 10,osStderr);
		else
			putc('>',osStderr);
		break;
	   }
	   case PgBusyFollow:	putc('.',osStderr); break;
	   case PgForeign:	putc('/',osStderr); break;
	   case PgPgMap:	putc('G',osStderr); break;
	   case PgBTree:	putc('T',osStderr); break;
	   case PgDLL:		putc('L',osStderr); break;
	   default:		putc('?',osStderr); break;
	}
}

putc('\n',osStderr);
}


/* Key to the symbols used in the pagemap display */
if (stoDetail & STO_SHOW_PAGEKEY0x00000080)
{
fprintf(osStderr, "| %-11s\n", "Symbols:");
fprintf(osStderr, "| %8s : %s\n",
	"+", "free page");
fprintf(osStderr, "| %8s : %s\n", 
	"[0-9]", "fixed-size pages by piece size");
fprintf(osStderr, "| %8s : %s\n", 
	"[a-f]", "fixed-size pages by piece size");
fprintf(osStderr, "| %8s : %s\n", 
	">", "fixed-size pages with large pieces");
fprintf(osStderr, "| %8s : %s\n", 
	"m", "mixed-size page");
fprintf(osStderr, "| %8s : %s\n", 
	".", "mixed-size pages for rest of large object");
fprintf(osStderr, "| %8s : %s\n", 
	"/", "foreign (not owned by us)");
fprintf(osStderr, "| %8s : %s\n", 
	"G", "holds the page map");
fprintf(osStderr, "| %8s : %s\n", 
	"T", "btree storage (mixed-page housekeeping)");
fprintf(osStderr, "| %8s : %s\n", 
	"L", "dll storage (mixed-page housekeeping)");
fprintf(osStderr, "| %8s : %s\n", 
	"?", "unknown page type");
}


/* Display the memory map of this process */
if (stoDetail & STO_SHOW_MEMMAP0x00000100)
{
              fprintf(osStderr, "| Heap....... [%p..%p) %ldK\n",
                      (void *) heapStart, (void *) heapEnd,
                      ptrDiff(heapEnd, heapStart)((long)((char *)(heapEnd) - (char *)(heapStart)))/1024);

              for (mm=osMemMap(OSMEM_DDATA0x02); (*mm)->use != OSMEM_END0x00; mm++)
                      fprintf(osStderr, "| Dyn memory: [%p..%p) %ldK\n",
                              (*mm)->lo, (*mm)->hi,
                              ptrDiff((*mm)->hi, (*mm)->lo)((long)((char *)((*mm)->hi) - (char *)((*mm)->lo)))/1024);
              for (mm=osMemMap(OSMEM_IDATA0x01); (*mm)->use != OSMEM_END0x00; mm++)
                      fprintf(osStderr, "| Init data:  [%p..%p) %ldK\n",
                              (*mm)->lo, (*mm)->hi,
                              ptrDiff((*mm)->hi, (*mm)->lo)((long)((char *)((*mm)->hi) - (char *)((*mm)->lo)))/1024);
              for (mm=osMemMap(OSMEM_STACK0x04); (*mm)->use != OSMEM_END0x00; mm++)
                      fprintf(osStderr, "| Stack:      [%p..%p) %ldbytes\n",
                              (*mm)->lo, (*mm)->hi,
                              ptrDiff((*mm)->hi, (*mm)->lo)((long)((char *)((*mm)->hi) - (char *)((*mm)->lo))));
}


/*
* If we are showing some output other than the census
* then we provide another separator to help the user.
*/
if (stoDetail & ~STO_SHOW_CENSUS0x00000400)
(void)fprintf(osStderr, "+%76.76s\n\n\n", sep);


/* Census of object types */
if (stoDetail & STO_SHOW_CENSUS0x00000400)
stoShowCensus(20);
4361}


4364/*
* Test consistency of storage management structures.
*/
4367void
4368stoAudit(void)
4369{
4370#ifndef NDEBUG
stoAuditAll();
4372#endif
4373}


4376/*
* Control storage manager behaviour.
*/

4380int
4381stoCtl(int cmd, ...)
4382{
va_list	argp;
int	rc;

va_start(argp, cmd)__builtin_va_start(argp, cmd);
rc = 0;

switch (cmd) {
case StoCtl_GcLevel1:
if (gcLevel != StoCtl_GcLevel_Never0)
	gcLevel = va_arg(argp, int)__builtin_va_arg(argp, int);
if (gcLevel == StoCtl_GcLevel_Never0)
	stoMustTag = false((int) 0);
break;
case StoCtl_GcFile2:
gcTraceFile   = va_arg(argp, FILE *)__builtin_va_arg(argp, FILE *);
break;
case StoCtl_Wash3:
stoMustWash   = va_arg(argp, Bool)__builtin_va_arg(argp, Bool);
break;
default:
rc = -1;
}

va_end(argp)__builtin_va_end(argp);
return rc;
4408}


4411void
4412stoRegister(StoInfo info)
4413{
if (info->code >= OB_MAX256)
bug("Too many object types");

stoObRegistered[info->code] = 1;
stoObNoInternalPtrs[info->code] = !info->hasPtrs;
4419}


4422/*
* Classify the specified pointer. This code is very shaky and needs
* to be checked more thoroughly. Do pointer comparisons work here?
*/
4426int
4427stoWritablePointer(Pointer p)
4428{
4429#if defined(OS_WIN32)
/* Win32 gives us a function specifically for this task */
return IsBadWritePtr(p, sizeof(long)) ? POINTER_IS_INVALID(-1) : POINTER_IS_VALID( 1);
4432#else
struct osMemMap **mm;
int	n;

/*
* Check if the target is in the heap. Unless the
* pointer is invalid then this is the most likely
* place to find the target object. We assume that
* all areas of the heap are writable.
*/
if (isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd))))) return POINTER_IS_VALID( 1);


/* Get the memory mappings */
mm = osMemMap(OSMEM_STACK0x04 | OSMEM_IDATA0x01 | OSMEM_DDATA0x02);


/* Can we classify this pointer at all? */
if (!mm) return POINTER_IS_UNKNOWN( 0);


/*
* Scan the whole memory map to find out where the
* target of this pointer lies. We assume that the
* stack, static and dynamic areas are all writable.
*/
for (n = 0 ; (*mm)->use != OSMEM_END0x00; mm++) {
switch ((*mm)->use) {
case OSMEM_STACK0x04:
	/* Is the object in this segment? */
	if (p < (Pointer)((*mm)->lo)) break;
	if (p > (Pointer)((*mm)->hi)) break;
	return POINTER_IS_VALID( 1);
case OSMEM_IDATA0x01:
	/* Is the object in this segment? */
	if (p < (Pointer)((*mm)->lo)) break;
	if (p > (Pointer)((*mm)->hi)) break;
	return POINTER_IS_VALID( 1);
case OSMEM_DDATA0x02:
	/* Is the object in this segment? */
	if (p < (Pointer)((*mm)->lo)) break;
	if (p > (Pointer)((*mm)->hi)) break;
	return POINTER_IS_VALID( 1);
	break;
  default:
	assert(false)do { if (!(((int) 0))) _do_assert(("false"),"store.c",4477); }
 while (0); /*mem type is silly*/
	break;
}
}


/* Can't find that pointer - assume invalid */
return POINTER_IS_INVALID(-1);
4485#endif
4486}


4489/*
* This is a somewhat dodgy function and is really only
* here for experimentation. It allows an Aldor domain
* to provide a call-back for marking itself during GC.
* Unless values from the domain occupy a lot of storage
* space with very few pointers it is extremely unlikely
* that this call back will be efficient. Not only that
* but the user must be extremely careful not to miss a
* potential pointer.
*/
4499void
4500stoSetAldorTracer(int code, Pointer clos)
4501{
if (code >= OB_MAX256)
bug("Too many object types");

if (!stoObRegistered[code])
bug("Object type not registered");

stoObAldorTracer[code] = (StoFiClos)clos;
4509}


4512/*
* This function performs exactly the same job as
* stoRegisterAldorTracer but is designed to be
* called from C.
*/
4517void
4518stoSetTracer(int code, StoTraceFun fun)
4519{
if (code >= OB_MAX256)
bug("Too many object types");

if (!stoObRegistered[code])
bug("Object type not registered");

stoObCTracer[code] = fun;
4527}


4530/*
* Given a pointer, try to mark the object pointed to.
* IMPORTANT: the code here must perform exactly the same
*            checks as the code in stoGcMarkRange(). We
*            don't do blacklisting though.
*/
4536int
4537stoMarkObject(Pointer p)
4538{
Pointer		*plo, *phi;
static int	pgno, qmno;
static PgInfo	pgtag;
static QmInfo	qmtag;
static Section *sect;
int		n = 0;
int		oldStoMarkArea = stoMarkArea;


/* Verify pointer is into heap. */
if (!isInHeap(p)((((Pointer)(heapStart)) <= ((Pointer)((p)))) && (
((Pointer)((p))) < ((Pointer)(heapEnd))))) return 0;
if (DEBUG(sto)((int) 0)) {stoMarkCount[stoMarkArea][PTR_INTO_HEAP0]++;}


/* Verify pointer is to busy page. */
pgno  = pgNo(p)(((long)((char *)((char *)(p)) - (char *)(heapStart))) >>
 12);
pgtag = pgMap[pgno];
if (pgtag != PgBusyFirst && pgtag != PgBusyFollow) return 0;
if (DEBUG(sto)((int) 0)) {
stoMarkCount[stoMarkArea][PTR_INTO_HEAP0]--;
stoMarkCount[stoMarkArea][PTR_INTO_BUSY1]++;
}


/* Grab section header. */
while (pgtag == PgBusyFollow) pgtag = pgMap[--pgno];
sect = sectAt(pgno)((Section *) ((Page *)((Pointer)((char *)(heapStart) + ((pgno
) * (1L<<12))))));


/* Verify pointed-to quantum. */
if (ptrLT(p, sect->data)(((Pointer)(p)) < ((Pointer)(sect->data)))) return 0;
if (DEBUG(sto)((int) 0)) {
stoMarkCount[stoMarkArea][PTR_INTO_BUSY1]--;
stoMarkCount[stoMarkArea][PTR_INTO_DATA2]++;
}


4576#ifdef STO_DIVISION_BY_LOOKUP1
/* If interior of object, point to beginning. */
/* Use shift operations where possible */
if (sect->isFixed)
{
       qmno = (sect->qmLog) ? qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog) : qmDivNo(p, sect)stoDivTable[(sect)->qmDiv][(((long)((char *)((char*)(p)) -
 (char *)((char*)((sect)->data)))))]; /* TTT */
assert(qmno == qmNo(p, sect))do { if (!(qmno == (((long)((char *)((char*)(p)) - (char *)((
char*)((sect)->data))))/(sect)->qmSize))) _do_assert(("qmno == qmNo(p, sect)"
),"store.c",4582); } while (0);
p = (sect->qmLog) ? ptrOff((char *) sect->data, qmno << sect->qmLog)((Pointer)((char *)((char *) sect->data) + (qmno << sect
->qmLog))) : 
  ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
}
else
{
qmno  = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
p = ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
}
4591#else
/* If interior of object, point to beginning. */
/* Use shift operations where possible */
if (sect->isFixed && sect->qmLog) {
qmno = qmLogNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
)))) >> (sect)->qmLog);
p = ptrOff((char *) sect->data, qmno << sect->qmLog)((Pointer)((char *)((char *) sect->data) + (qmno << sect
->qmLog)));
}
else {
qmno  = qmNo(p, sect)(((long)((char *)((char*)(p)) - (char *)((char*)((sect)->data
))))/(sect)->qmSize);
/* If interior of object, point to beginning. */
p = ptrOff((char *) sect->data, qmno * sect->qmSize)((Pointer)((char *)((char *) sect->data) + (qmno * sect->
qmSize)));
}
4603#endif


/* Verify not already marked. */
qmtag = sect->info[qmno];
if (QmInfoMark(qmtag)((qmtag) & 0x20)) return 0;
if (DEBUG(sto)((int) 0)) {
stoMarkCount[stoMarkArea][PTR_INTO_DATA2]--;
stoMarkCount[stoMarkArea][PTR_INTO_NEW3]++;
}


/* Add mark bits quanta in piece.  Determine data bounds. */
if (sect->isFixed) {
QmInfoSetMark(sect->info[qmno])((sect->info[qmno]) |= 0x20);
plo = (Pointer *) p;
phi = (Pointer *) ptrOff((char *) plo, sect->qmSize)((Pointer)((char *)((char *) plo) + (sect->qmSize)));
}
else {
MxMem	*pc;
int	sz, nq, qi;

while (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmFollow0x00)
	qmtag = sect->info[--qmno];

pc = (MxMem *)ptrOff((char *)sect->data,((Pointer)((char *)((char *)sect->data) + (qmno*sect->qmSize
)))
		     qmno*sect->qmSize)((Pointer)((char *)((char *)sect->data) + (qmno*sect->qmSize
)));
sz = pc->nbytesThis;
nq = sz/sect->qmSize;

for (qi = qmno; qi < qmno + nq; qi++)
	QmInfoSetMark(sect->info[qi])((sect->info[qi]) |= 0x20);

sz -= MxMemHeadSize(sizeof(MxMem) - sizeof(MxMemU));
plo = (Pointer *) (&pc->body.busy.data);
phi = (Pointer *) ptrOff((char *) plo, sz)((Pointer)((char *)((char *) plo) + (sz)));
}


/* Verify piece is in use. */
if (QmInfoKind(qmtag)((qmtag) & 0xC0) == QmFreeFirst0x40) {
if (DEBUG(sto)((int) 0)) {
	stoMarkCount[stoMarkArea][PTR_INTO_NEW3]--;
	stoMarkCount[stoMarkArea][PTR_INTO_FREE4]++;
}
stoGcMarkedFree++;
return 0;
}


/* Check that this contains pointers 
* This test should use a bit in the tag, not the code.
*/
if (QmIsPtrFree(qmtag)(stoObNoInternalPtrs[((qmtag) & 0x1F)])) return 0;


/* We have marked this piece */
n++;


4663#if STO_USER_CAN_TRACE
/*
* Has the creator of this object requested
* permission to trace it?
*/
if (QmAldorTraced(qmtag)(stoObAldorTracer[((qmtag) & 0x1F)]))
{
/* Invoke the creator's tracer */
n += (int)stoFiCCall2(int, QmAldorTraced(qmtag), plo, phi)((*((int (*)())((stoObAldorTracer[((qmtag) & 0x1F)]))->
prog->fun))(((stoObAldorTracer[((qmtag) & 0x1F)]))->
env,plo,phi));
return n;
}
if (QmCTraced(qmtag)(stoObCTracer[((qmtag) & 0x1F)]))
{
/* Invoke the creator's tracer */
n += (QmCTraced(qmtag)(stoObCTracer[((qmtag) & 0x1F)]))(plo, phi);
return n;
}
4680#endif


/* Pointer classification */
if (DEBUG(sto)((int) 0)) {
if (stoMarkArea < MEM_MAX_TYPE(3 +1)) {
	/* Now marking within heap */
	oldStoMarkArea = stoMarkArea;
	stoMarkArea += MEM_MAX_TYPE(3 +1);
}
}


/* Count the number of children marked */
n += stoGcMarkRange(plo, phi, (int) 0);


/* Pointer classification */
if (DEBUG(sto)((int) 0)) {stoMarkArea = oldStoMarkArea;}

return n;
4701}


4704/*
* Exception handling code.
*/

4708localstatic MostAlignedType *
4709stoDefaultError(int errnum)
4710{
String msg;

switch (errnum) {
case StoErr_OutOfMemory1:  return 0;
case StoErr_UsedNonalloc2: msg = "using non-allocated space";	  break;
case StoErr_CantBuild3:	  msg = "can't build internal structure"; break;
case StoErr_FreeBad4:      msg = "attempt to free unknown space";  break;
default:		  msg = "unexpected";			  break;
}
fprintf(osStderr, "Storage allocation error (%s).\n", msg);
exitFailure();
NotReached(return 0){(void)bug("Not supposed to reach line %d in file: %s\n",4722
, "store.c");};
4723}

4725StoErrorFun
4726stoSetHandler(StoErrorFun f)
4727{
StoErrorFun oldf = stoError;
stoError = f ? f : (StoErrorFun) stoDefaultError;
return oldf;
4731}

4733/*===========================================================================*/

4735#else /* not STO_USE_BTREE */

4737/*
* Alternate storage management schemes are based on three functions:
*    stoMore, stoLess, and stoMoreOrLess.
*/

4742#ifdef STO_USE_MALLOC
4743extern	Pointer malloc	(Length);
4744extern	void	free	(Pointer);

4746# define stoMore(sz)		  ((Pointer) malloc(sz))
4747# define stoMoreOrLess(p,osz,nsz) ((Pointer) realloc(p, nsz))
4748# define stoLess(p)		  free(p)
4749#endif

4751#ifdef STO_USE_BOEHM
4752/* uncomment this */
4753#include <gc/gc.h>

4755# define stoMore(sz)               ((Pointer) GC_malloc(sz))
4756# define stoMoreOrLess(p,osz,nsz)  ((Pointer) GC_realloc(p,nsz))
4757# define stoLess(p)                GC_free(p)
4758#endif



4762#ifdef STO_USE_ONCE
4763localstatic Pointer
4764stoMore(Length sz)
4765{
static long	stoC = 0;
static char *	stoV;
Pointer		r;

sz = ROUND_UP(sz, alignof(MostAlignedType))((sz) % ((sizeof(struct {char a; MostAlignedType b;}) - sizeof
(MostAlignedType))) ? (sz) + ((sizeof(struct {char a; MostAlignedType
 b;}) - sizeof(MostAlignedType))) - (sz) % ((sizeof(struct {char
 a; MostAlignedType b;}) - sizeof(MostAlignedType))) : (sz));
if (sz > stoC) {
ULong	L = MAX(sz, ((long) 1) << 15)((sz) > (((long) 1) << 15) ? (sz) : (((long) 1) <<
 15));
Pointer P = osAlloc(&L);
if (!P) return 0;
stoC = L; stoV = (char *) P;
}
r =  (Pointer) stoV; stoC -= sz; stoV += sz;
return r;
4779}
4780localstatic Pointer
4781stoMoreOrLess(Pointer p, Length osz, Length nsz)
4782{
Pointer		r;

if (osz >= nsz) return p;
r = stoMore(nsz);
if (r) memmove(r, p, osz);
return r;
4789}
4790# define stoLess(p)	((void) (p))
4791#endif

4793/*
* The remainder is common to all alternate implementations.
*/


4798static Bool    stoMustTag    = false((int) 0);

4800ULong	       stoBytesOwn   = 0;	/* Total owned by allocator. */
4801ULong	       stoBytesAlloc = 0;	/* Total ever allocated.  */
4802ULong	       stoBytesFree  = 0;	/* Total ever freed. */
4803ULong	       stoBytesGc    = 0;	/* Total ever garbage collected. */
4804ULong	       stoPiecesGc[STO_CODE_LIMIT32];	/* # this time, by code. */

4806#ifdef STO_TALLY
4807# define stoTally(expr)(expr)		(expr)
4808#else
4809# define stoTally(expr)(expr)		Nothing
4810#endif

4812struct stoHdr {
char		code;
unsigned short	magic;
Length		size;
MostAlignedType data;
4817};

4819# define STO_MAGIC	0xFE20 /* Any unlikely 2 byte sequence. */

4821# define sizeofHdr	(sizeof(struct stoHdr) - sizeof(MostAlignedType))
4822# define stoPtrToHdr(p) ((struct stoHdr *)((char *) p - sizeofHdr))
4823# define stoHdrToPtr(h) ((Pointer) &((h)->data))

4825localstatic MostAlignedType * stoDefaultError	 (int errnum);
4826static StoErrorFun	stoError	 = stoDefaultError;

4828MostAlignedType *
4829stoAlloc(unsigned code, ULong size)
4830{
Length		sz = size + sizeofHdr;
Pointer		p;
struct stoHdr	*q;

if (sz == 0) sz = 1;	/* For malloc. */

p = stoMore(sz);
if (!p) return (*stoError)(StoErr_OutOfMemory1);

q = (struct stoHdr *) p;
p = stoHdrToPtr(q);

if (stoMustTag) {
q->code  = code;
q->magic = STO_MAGIC;
}
stoTally(stoBytesAlloc += size)(stoBytesAlloc += size);
q->size	 = sz;
return (MostAlignedType *) p;
4850}

4852void
4853stoFree(Pointer p)
4854{
if (p==NULL((void*)0))
return;
stoTally(stoBytesFree += stoPtrToHdr(p)->size)(stoBytesFree += stoPtrToHdr(p)->size);
stoLess(stoPtrToHdr(p));
4859}

4861ULong
4862stoSize(Pointer p)
4863{
return stoPtrToHdr(p)->size - sizeofHdr;
4865}

4867unsigned
4868stoCode(Pointer p)
4869{
int	c = 0;
if (stoMustTag)
c = stoPtrToHdr(p)->code;
return c;
4874}

4876MostAlignedType *
4877stoResize(Pointer p0, ULong size)
4878{
struct stoHdr	*q0, *q1;
Length		nsz = size + sizeofHdr;

q0 = stoPtrToHdr(p0);
q1 = (struct stoHdr *) stoMoreOrLess(q0, q0->size, nsz);
if (!q1) return (*stoError)(StoErr_OutOfMemory1);
q1->size = nsz;

return (MostAlignedType *) stoHdrToPtr(q1);
4888}

4890MostAlignedType *
4891stoRecode(Pointer p, unsigned code)
4892{
if (stoMustTag) stoPtrToHdr(p)->code = code;
return (MostAlignedType *) p;
4895}

4897Bool
4898stoIsPointer(Pointer p)
4899{
int	isMagic = 1;
if (!p) return 0;
if (stoMustTag) isMagic = stoPtrToHdr(p)->magic == STO_MAGIC;
return isMagic;
4904}

4906void stoGc			(void)		{ }
4907void stoTune			(void)		{ }
4908int  stoShowArgs		(char *detail)	{ return 0; }
4909void stoShow			(void)		{ }
4910void stoShowDetail		(int x)		{ }
4911void stoAudit			(void)		{ }
4912void stoRegister		(StoInfo info)	{ }
4913void stoSetAldorTracer		(int code, Pointer clos) {}
4914void stoSetTracer		(int code, StoTraceFun fun) {}
4915int  stoMarkObject		(Pointer p)	{ return 0; }
4916int  stoWritablePointer		(Pointer p)	{ return POINTER_IS_UNKNOWN( 0); }
4917int  stoCtl			(int cmd, ...)	{ return 0; }

4919static struct tmTimer gcTimer;
4920TmTimer stoGcTimer		(void) { return &gcTimer; }


4923/*
* Exception handling code.
*/
4926localstatic MostAlignedType *
4927stoDefaultError(int errnum)
4928{
String msg;
switch (errnum) {
case StoErr_OutOfMemory1:
return 0;
case StoErr_UsedNonalloc2:
msg = "using non-allocated space";
break;
case StoErr_CantBuild3:
msg = "can't build internal structure";
break;
default:
msg = "unexpected";
break;
}
fprintf(osStderr, "Storage allocation error (%s).\n", msg);
exitFailure();
NotReached(return 0){(void)bug("Not supposed to reach line %d in file: %s\n",4945
, "store.c");};
4946}

4948StoErrorFun
4949stoSetHandler(StoErrorFun f)
4950{
StoErrorFun oldf = stoError;
stoError = f ? f : (StoErrorFun) stoDefaultError;
return oldf;
4954}

4956#endif /* !STO_USE_BTREE */