Rick's b.log - entry 2016/08/01

Walking the RMA

A long time ago, a big clue was given to me by an errant module that was writing data beyond its allocation. This corrupted some things, leading subsequent actions on the module area to fail with a message such as "Not a heap block". I don't remember the exact text, but something came together in my head.

The truth is that the RMA is a large resizable memory zone (old Archimedes) or Dynamic Area (RiscPC and later) which contains a chained list of OS_Heap blocks. The blocks are laid out such that the word immediately prior to the block pointer gives an offset that points to the next object except for if this is a "free block" in which case the word pointed to gives the size of the free block (and is thus implicitly the pointer to the next block) which the regular offset pointer points to the next free block.
Yes, you have to keep track of both in tandem.

The end of the list is supposed to be denoted by the pointer being zero to mark the end of the list. I have seen it as zero, but I have also seen it as wildly bogus values. I guess I'm maybe reading something wrong here, I don't know. So I terminate the list if the pointer is zero, if the eventual address is beyond the end of the RMA, or if the eventual address is a negative number (as would be the case of adding &80000000 or more to the pointer - integers are signed in BASIC).

You might be saying "Hey, wait, Reporter can do this!". You're right, Reporter can, in a nice clicky-pointy sort of way too. However we have two benefits:

• Because of Reporter's user interface, there's no way you can easily see four thousand blocks listed. It can be done, by turning on the logging and restarting Reporter, but it takes about four times as long as typing RMAwalker { > $.rmastuff } and letting my program dump the items which RISC OS then redirects output to a file on disc.
• Reporter doesn't attempt to be intelligent. It just lists allocated and freed blocks. My RMAwalker first collects the addresses of modules and their workspace and when listing objects it will try to match an address to indicate what is there.

&200096F4 :        32 Workspace : BlendTable
&20009714 :        32 Workspace : BufferManager
&20009734 :        64 
&20009774 :        64 
&200097B4 :       128 
&20009834 :       672 Workspace : Debugger

Don't take my word for it - here's the top and tail of my RMA dump:

Examining Module Area

RMA base  : &20000000
RMA size  : 4427776 bytes
RMA end   : &20439000
Free space: 278128 bytes (largest block is 229468 bytes)

&20000014 :       448 Workspace : PCI
&200001D4 :     5,312 Workspace : FileSwitch
&20001694 :        64 Workspace : ResourceFS
&200016D4 :       224 Workspace : TerritoryManager
&200017B4 :        32 
&200017D4 :     6,240 Workspace : MessageTrans
&20003034 :       480 

[...]

&2038BAF4 :     3,232 Free block
&2038C794 :       704 
&2038CA54 :       320 Free block
&2038CB94 :       224 
&2038CC74 :       160 Free block
&2038CD14 :       704 
&2038CFD4 :       224 
&2038D0B4 :        96 
&2038D114 :       160 
&2038D1B4 :       224 
&2038D294 :        96 
&2038D2F4 :       160 
&2038D394 :       224 
&2038D474 :       160 
&2038D514 :       224 
&2038D5F4 :     3,616 
&2038E414 :       128 
&2038E494 :     1,280 Free block
&2038E994 :       384 
&2038EB14 :        32 Free block
&2038EB34 :       320 
&2038EC74 :       160 
&2038ED14 :       320 
&2038EE54 :       320 
&2038EF94 :       320 Free block
&2038F0D4 :       224 
&2038F1B4 :       992 
&2038F594 :       320 
&2038F6D4 :       416 
&2038F874 :       320 
&2038F9B4 :     1,152 
&2038FE34 :       320 
&2038FF74 :       160 
&20390014 :       320 
&20390154 :       320 
&20390294 :       192 
&20390354 :       672 
&203905F4 :       320 
&20390734 :        64 Free block
&20390774 :       160 
&20390814 :       640 
&20390A94 :       320 
&20390BD4 :       256 
&20390CD4 :       384 
&20390E54 :       320 
&20390F94 :        96 Free block
&20390FF4 :       192 
&203910B4 :       320 
&203911F4 :       320 
&20391334 :       448 
&203914F4 :       320 
&20391634 :       352 
&20391794 :       352 
&203918F4 :       320 
&20391A34 :       704 
&20391CF4 :       320 
&20391E34 :       320 
&20391F74 :       320 
&203920B4 :       320 
&203921F4 :       320 
&20392334 :       320 
&20392474 :    21,216 
&20397754 :       320 
&20397894 :       320 
&203979D4 :       320 
&20397B14 :       320 
&20397C54 :       320 
&20397D94 :       320 
&20397ED4 :       320 
&20398014 :       320 
&20398154 :       320 
&20398294 :        96 Free block
&203982F4 :     1,056 
&20398714 :     2,176 
&20398F94 :     4,128 
&20399FB4 :        32 Free block
&20399FD4 :     2,176 
&2039A854 :     4,128 
&2039B874 :     9,440 Workspace : StrongHelp
&2039DD54 :    11,072 Module    : ZapTaskWindow
&203A0894 :       448 Free block
&203A0A54 :     2,176 
&203A12D4 :    34,528 Module    : ZapMJE
&203A99B4 :    21,728 Module    : ABCLibrary
&203AEE94 :    15,616 Module    : eXML
&203B2B94 :    16,416 Workspace : eXML
&203B6BB4 :    22,048 Module    : VideoUtils
&203BC1D4 :    21,792 Workspace : VideoUtils
&203C16F4 :     1,056 Free block
&203C1B14 :     2,368 
&203C2454 :     1,312 
&203C2974 :     4,128 
&203C3994 :     2,368 
&203C42D4 :     2,368 
&203C4C14 :     2,400 Free block
&203C5574 :     6,304 Workspace : !Edit
&203C6E14 :     2,368 
&203C7754 :     2,304 
&203C8054 :    41,152 Module    : ZapBASIC
&203D2114 :    37,856 
&203DB4F4 :    16,320 Module    : LineEditor
&203DF4B4 :    54,176 Module    : StrongHelp
&203EC854 :    29,120 Free block
&203F3A14 :     4,128 
&203F4A34 :     2,368 
&203F5374 :     2,368 
&203F5CB4 :     2,368 Free block
&203F65F4 :     1,312 
&203F6B14 :     4,128 
&203F7B34 :     2,368 
&203F8474 :     4,128 
&203F9494 :     2,368 
&203F9DD4 :     1,312 
&203FA2F4 :     4,128 
&203FB314 :     2,368 
&203FBC54 :     1,312 
&203FC174 :     4,128 
&203FD194 :     2,368 
&203FDAD4 :     1,312 
&203FDFF4 :     4,128 
&203FF014 :   229,472 Free block
&20437074 :     4,128 
&20438094 :     3,952 Unused space

Listed 3474 allocated blocks totalling 4,149,952 bytes,
and 46 free blocks totalling 277,808 bytes.

Now on to some code. Yay!

I won't be annotating the code, the comments should be sufficient. Copy-paste the program code into !Edit, set the file's type to be "BASIC" and then save the program as "RMAwalker".

REM >RMAwalker
REM Walk the RMA
REM
REM By Rick Murray, 2016/08/01
REM
REM Open Source software - this code has been released under the EUPL v1.1 (only).
REM https://joinup.ec.europa.eu/community/eupl/og_page/european-union-public-licence-eupl-v11
REM

REM Allocate memory for up to 256 modules
DIM modbase%(256)
DIM modwksp%(256)
DIM modname$(256)
modmax% = 0            : REM How many modules we found
alloccount% = 0        : REM Count of allocated blocks
freecount% = 0         : REM Count of free blocks
allocsize% = 0         : REM Size of allocated blocks
freesize% = 0          : REM Size of free blocks
DIM buffer% 15         : REM Buffer for pretty number formatting

REM Zero module data blocks
FOR recurse% = 0 TO 255
  modbase%(recurse%) = 0
  modwksp%(recurse%) = 0
  modname$(recurse%) = ""
NEXT

REM Get RMA boundaries (RMA is DA 1; this will fail on old RISC OS)
SYS "OS_DynamicArea", 2, 1 TO ,, rmasize%, rmabase%
rmaend% = rmabase% + rmasize%
SYS "OS_Module", 5 TO ,,rmalargest%, rmafree%

REM Header text
PRINT "Examining Module Area"
PRINT
PRINT "RMA base  : &"+STR$~(rmabase%)
PRINT "RMA size  : "+STR$(rmasize%)+" bytes"
PRINT "RMA end   : &"+STR$~(rmaend%)
PRINT "Free space: "+STR$(rmafree%)+" bytes";
PRINT " (largest block is "+STR$(rmalargest%)+" bytes)"
PRINT

REM Read module information
REM We only look at first 255 modules so we don't risk overrun
FOR recurse% = 0 TO 255
  SYS "XOS_Module", 12, recurse% TO ,,,modptr%, modpw% ; f%
  IF ((f% AND 1) = 0) THEN
    REM Didn't fault, so we have module information
    valid% = FALSE

    REM Is the module itself in the RMA? (otherwise ROM)
    IF ( (modptr% > rmabase%) AND (modptr% < rmaend%) ) THEN
      modbase%(modmax%) = modptr%
      valid% = TRUE
    ENDIF

    REM Is the workspace in the RMA? (otherwise a DA, no workspace, etc)
    IF ( (modpw% > rmabase%) AND (modpw% < rmaend%) ) THEN
      modwksp%(modmax%) = modpw%
      valid% = TRUE
    ENDIF

    REM If valid is TRUE, then module and/or workspace is in RMA, so retrieve modname
    REM (icky hack time)
    IF (valid% = TRUE) THEN
      SYS "XOS_GenerateError", (modptr% + modptr%!16) TO name$
      modname$(modmax%) = name$

      modmax% += 1
    ENDIF
  ENDIF
NEXT

REM Verify the heap is a heap (paranoid!)
IF (rmabase%!0 <> &70616548) THEN ERROR 1, "RMA not a Heap?"

REM Calculate "first free block"
rmanextfree% = (rmabase% + rmabase%!4 + 8)

REM Try walking the heap...
this% = rmabase% + &14

REPEAT
  nextptr% = this%!-4
  isfree% = FALSE
  endoflist% = FALSE

  REM Fudge things if this is a free block
  IF (this% = rmanextfree%) THEN
    REM PRINT this%!-4, this%!0, this%!4
    rmanextfree% += nextptr% : REM Set free pointer to next free object
    nextptr% = this%!0       : REM Set next item appropriately here
    isfree% = TRUE
  ENDIF

  REM If next pointer is zero, we'll need some more fudging.
  IF (nextptr% = 0) THEN
    endoflist% = TRUE
    nextptr% = (rmaend% - this%) + 4
  ENDIF

  REM More fudging if nextptr% is bogus and following it will make us blow up
  REM Sometimes we don't always reach the end of the heap tidily.
  REM Not sure what the difference is, suffice to say that Reporter may see an
  REM unused block of 40,848 bytes in size. We, however, are likely to see the
  REM same as two blocks - in this case 4,128 bytes and 36,720 bytes; with the
  REM nextptr being something gibberish.
  test% = this% + nextptr%
  IF ( (test% > rmaend%) OR (test% < 0) ) THEN
    REM Same as just above
    endoflist% = TRUE
    nextptr% = (rmaend% - this%) + 4
  ENDIF

  REM It's an allocation unless we know otherwise
  alloccount% += 1
  allocsize% += nextptr%

  REM Print what we've found   (up to "9,999,999")
  PRINT "&"+STR$~(this%)+" : ";
  PRINT RIGHT$("         "+FNprettynum(nextptr%), 9)+" ";

  REM Is this a module?
  FOR recurse% = 0 TO (modmax% - 1)
    IF (modbase%(recurse%) = this%) THEN
      PRINT "Module    : "+modname$(recurse%);
    ENDIF
  NEXT

  REM Is this workspace?
  FOR recurse% = 0 TO (modmax% - 1)
    IF (modwksp%(recurse%) = this%) THEN
      PRINT "Workspace : "+modname$(recurse%);
    ENDIF
  NEXT

  REM Is it a free block?
  IF (isfree% = TRUE) THEN
    PRINT "Free block";
    alloccount% -= 1
    allocsize% -= nextptr%
    freecount% += 1
    freesize% += nextptr% : REM Fudge factor
  ENDIF

  REM Is this the end of the list?
  IF (endoflist% = TRUE) THEN
    PRINT "Unused space";
    alloccount% -= 1
    allocsize% -= nextptr%
    freecount% += 1
    freesize% += nextptr%
    nextptr% = 0 : REM Reset next object pointer to zero
  ENDIF

  REM Give a linefeed to end whatever printed
  PRINT

  REM Point to the next item
  this% += nextptr%

UNTIL (nextptr% = 0)

REM Print a summary.
REM Note that our free block bytes will NOT match the value returned by OS_Module.
PRINT
PRINT "Listed "+STR$(alloccount%)+" allocated blocks totalling "+FNprettynum(allocsize%)+" bytes,"
PRINT "and "+STR$(freecount%)+" free blocks totalling "+FNprettynum(freesize%)+" bytes."

END

DEFFNprettynum(what%)
  SYS "OS_ConvertSpacedCardinal4", what%, buffer%, 16 TO ,term%
  term%?0 = 13
  FOR recurse% = buffer% TO term%
    IF recurse%?0 = 32 THEN recurse%?0 = 44
  NEXT
=$buffer%

Some ideas (exercises for the reader):

• Keep scanning modules until we run out of allocation space - not all modules are in the RMA or have workspace in the RMA (SharedCLibrary, for example).
• The address matching is horribly inefficient. It scans each list of addresses entirely; if a match is found it should stop at that point. Probably easiest to do by making that bit of code a PROC so you can just ENDPROC when you're done.

And finally? You'll be surprised at exactly how much rubbish is in the RMA. And a little depressed that Acorn's OS_Heap SWI never included a mechanism to walk ("enumerate") the heap. Plus it is a shame that the RMA code doesn't tag claims with a backpointer (return R14?) to what made the claim; but back in '85 these sorts of things were likely not thought of and besides memory was expensive. Three and a half thousand blocks, a word extra apiece, that's about 14KiB. That could be a lot on a 1MiB machine.

Your comments:

Please note that while I check this page every so often, I am not able to control what users write; therefore I disclaim all liability for unpleasant and/or infringing and/or defamatory material. Undesired content will be removed as soon as it is noticed. By leaving a comment, you agree not to post material that is illegal or in bad taste, and you should be aware that the time and your IP address are both recorded, should it be necessary to find out who you are. Oh, and don't bother trying to inline HTML. I'm not that stupid! ☺ ADDING COMMENTS DOES NOT WORK IF READING TRANSLATED VERSIONS.
 
You can now follow comment additions with the comment RSS feed. This is distinct from the b.log RSS feed, so you can subscribe to one or both as you wish.

Anon, 3rd August 2016, 10:35

The RMA... what a horrible hack. I guess in the days of 1MB RAM and the system being used for a bit then switched off it wasn't a problem. The computer got rebooted before the RMA got fragmented.    By the time I had a RISC PC with 128MB of RAM, RMA fragmentation had become a serious problem. Most newer apps used dynamic areas where they were available. A few older ones didn't. Those apps cause the problem.    (I'm writing this on a PC with a 6-core 64-bit CPU, 32GB of RAM and a 1TB SSD... how times change!)

David Pilling, 10th August 2016, 02:49

Any chance of taking an off the shelf (open source etc) memory manager and producing a new module.  I set off reading this thinking I'd been involved at some point, but I think that was with how C malloc works. In my efforts I never used OS_Heap - unless there was no alternative or you're about to point out that C malloc just passes everything on to OS_heap.

Add a comment (v0.11) [help?] . . . try the comment feed!
		Your name
		Your email	(optional)
		Validation	Are you real? Please type 77998 backwards.
		Your comment