#45 6.4.2 `progn$` freed a value the loop had not reached

[Batch Job 1]

progn$ freed a value the loop had not reached

What happened. A progn$ or foreach whose multifield is written as an inline expression, nested inside another such loop, with an action that rebinds a variable, read freed memory part way along the multifield.

(deffunction counted (?factor)
   (bind ?running 0)
   (progn$ (?outer (create$ one two three four))
      (progn$ (?element (create$ (* ?factor 1) (* ?factor 7) (* ?factor 8)
                                 (* ?factor 9) (* ?factor 10) (* ?factor 2)
                                 (* ?factor 11) (* ?factor 12)))
         (if (integerp ?element) then (bind ?running (+ ?running ?factor)))))
   (printout t "counted " ?running crlf))
(counted 1000000)

halted with

[ARGACCES2] Function 'integerp' expected argument #1 to be of type integer, float, symbol, ... or multifield.
[PRCCODE4] Execution halted during the actions of deffunction 'counted'.

?element is an integer at every step of that loop. Printing it printed an integer, summing it summed, and walking the multifield without touching it reached the end. The type integerp objected to was void, read out of a reused allocation. Replacing integerp with the addition that sums the elements moved the diagnostic to + and its second argument: the function named is whichever one first inspects the field variable, which is not where the fault is.

Why it is a fix and not a preference. The Basic Programming Guide gives progn$ the grammar

<multifield-spec> ::= <multifield-expression> |
                      (<field-variable> <multifield-expression>)

so an expression in that position is what the function is documented to accept, and it says "The field of the current iteration can be examined with the <field-variable> term". A field that has been deallocated cannot be examined. foreach is documented to provide "the same functionality".

Where it came from. Three pieces, each correct alone.

MultifieldPrognDriver in multifun.c evaluates its first argument into a local UDFValue, then garbage collects after every action:

   if (! UDFFirstArgument(context,MULTIFIELD_BIT,&argval))
     { ... }

   GCBlockStart(theEnv,&gcb);
   ...
         if (((i + 1) < end) || (theExp->nextArg != NULL))
           {
            CleanCurrentGarbageFrame(theEnv,NULL);
            CallPeriodicTasks(theEnv);
           }

The NULL says nothing needs protecting, and nothing holds argval.

A multifield in the garbage list does not own the values in it. FlushMultifields frees one on its own busyCount without touching its contents, and a multifield is built by assigning to contents[i].value with no reference taken — StringToMultifield and StoreInMultifield, which are what explode$ and create$ run, both do exactly that.

bind releases whatever the variable held before. PutProcBind in prccode.c:

      if (dst->supplementalInfo == TrueSymbol(theEnv))
        ReleaseUDFV(theEnv,dst);

Put together: one interned integer or symbol reached from two places is one reference counted object, so when the counter's previous value is also an element of the multifield being walked, that release takes the element's count to zero. ReleaseInteger then files the atom under whichever garbage frame is current, which inside the actions is the loop's own frame, and the collection quoted above frees it. The loop reads it at

      tmpField->type = argval.multifieldValue->contents[i].header->type;

Marking will not carry the value through this. RemoveEphemeralHashNodes clears markedEphemeral from any atom it finds with a count above zero and drops it from the list, so an atom the counter is holding at the time of a collection comes out unmarked and can be filed under a deeper frame on its next release. Only a reference held for the length of the loop prevents the free.

The change. MultifieldPrognDriver takes a reference to the multifield and to the atomic values in it for as long as it walks it, through RetainPrognMultifield, and lets them go on both exits through ReleasePrognMultifield. No element's count can reach zero while the loop is live.

That is what the multifield bound to a variable already had, by way of the retain at the end of PutProcBind — which is why only the inline form was affected, and why binding the multifield to a variable first worked before the cause was known.

What the reference covers, and what it leaves alone. Fact and instance addresses are not retained. The garbage fact and instance lists, together with the loop's own GCBlock, already keep a retracted fact or a deleted instance alive for as long as the loop can reach it, and that is how CLIPS was already correct for them.

This started as the blanket RetainUDFV, which retains every element whatever its type, and that was wrong for a reason nothing about correctness showed. A retained fact is out of reach of the CleanCurrentGarbageFrame the loop runs on each pass, so a loop that retracted what it walked left every retraction on the garbage fact list, and the walk of that list on each pass made the loop quadratic in the number of fields. (progn$ (?found (find-all-facts ((?r reading)) TRUE)) (retract ?found)) is an ordinary CLIPS idiom, and it measured:

facts	before this fix	with the blanket retain	as it now stands
500	0.00007 s	0.00015 s	0.00017 s
8000	0.00078 s	0.04825 s	0.00096 s

Sixteen times the facts cost three hundred and twenty-five times the time in the middle column, and the two outer columns grow with the facts.

The types are recorded when the reference is taken rather than read back when it is let go. A fact the loop retracted can be freed before the loop ends, which leaves that field pointing at memory whose type can no longer be read — reading it back is what the first attempt at the narrowing did, and it corrupted the reference counts.

What was checked. The nested loop above, in both the progn$ and the foreach spelling. The elements summed as well as counted, so an element standing for a different value would be caught and not only one standing for nothing. The multifield bound to a variable first, which must stay as it was. One level of looping, which was already clean and stays clean; a single loop did not reproduce it under AddressSanitizer either.

For the reference being let go: break and return out of the loop, and twenty thousand rounds of an early exit, which grows memory in use by nothing. Removing the release on the early exit path alone grows that same run by 5 760 000 bytes, so the check reports.

The tests here are a guard, not the report. They pass against a build with the retain removed altogether, so a passing run of run-fix-tests.sh does not on its own establish that the fix is in place. What discriminates is AddressSanitizer with -DMEM_TABLE_SIZE=0 over tests/inline-multifield.clp, across three source trees:

tree	what AddressSanitizer reports
unmodified 6.4.2	heap-use-after-free
this fix as it stands	nothing
this fix with the retain removed	heap-use-after-free

The third row is the one that matters: without it, the second row would be consistent with the reproducer no longer reaching the defect at all.

The reason to care about this one: the shape that triggers it is a plain nested read loop, the shape that evades it is a bind on the line above, and nothing in the diagnostic points at either.

Present in 7.0? Not checked.