[PATCH][RFC] check for heap memory in zfree()

[PATCH][RFC] check for heap memory in zfree()

[Andrey Borzenkov]

[-- Attachment #1.1: Type: text/plain, Size: 1734 bytes --]

I did not receive my previous mail so I am not sure if it was ever 
delivered ...

On Saturday 04 March 2006 11:04, Andrey Borzenkov wrote:
> [moved to workers]
>
> On Thursday 02 March 2006 20:52, Francisco Borges wrote:
> > % typeset -U dirstack
> >
> > and the shell crashed.
>
> The problem is rather non-trivial. dirsgetfn returns array built on-the-fly
> in heap, while typeset -U calls uniqarray() that tries to zfree array
> elements. There are at least two problems here:
>
> - typeset -U is not prepared to deal with "pseudo" parameters at all. It
> assumes a->getfn() returns pointer to real parameter value. So it would
> have not worked for dirstack anyway
>
> - I was about to change typeset -U to pm->gsu.a->setfn(pm,
> pm->gsu.a->getfn(pm)) (basically doing foo=($foo)) and adding uniqarray
> call to dirssetfn() when I realized that it would not help at all in this
> case as dirssetfn() tries to free passed value too; so it would have
> crashed just the same.
>
> Apparently to solve it in general we need one of
>
> - per-parameter type ->uniq function (is it an overkill?) Possibly
> generalized to per-parameter ->setflags function.
>
> - some way to know if passed pointer was allocated from heap or not. I
> guess it should be possible; something like isheap(p)?
>

OK attached is patch that checks if memory has been allocated from heap. 
Comments on whether it makes sense? I am rather concerned that it may hide 
real problem sometimes (i.e. instead of crashing right away memory that was 
_supposed_ to be permanently allocated may end up in heap and be silently 
removed later; it is apparently harder to debug).

The patch does fix dirstack crash BTW.

-andrey

[-- Attachment #1.2: do_not_free_heap.patch --]
[-- Type: text/x-diff, Size: 1360 bytes --]

Index: Src/mem.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/mem.c,v
retrieving revision 1.12
diff -u -p -r1.12 mem.c
--- Src/mem.c	17 Jul 2004 19:25:14 -0000	1.12
+++ Src/mem.c	4 Mar 2006 08:51:40 -0000
@@ -1241,17 +1241,6 @@ free(FREE_ARG_T p)
 #endif
 }
 
-/* this one is for strings (and only strings, real strings, real C strings,
-   those that have a zero byte at the end) */
-
-/**/
-mod_export void
-zsfree(char *p)
-{
-    if (p)
-	zfree(p, strlen(p) + 1);
-}
-
 MALLOC_RET_T
 realloc(MALLOC_RET_T p, MALLOC_ARG_T size)
 {
@@ -1463,19 +1452,34 @@ bin_mem(char *name, char **argv, Options
 
 /**/
 mod_export void
-zfree(void *p, UNUSED(int sz))
+zfree(void *p, int sz)
 {
-    if (p)
+    Heap h;
+
+    if (!p)
+	return;
+
+    queue_signals();
+    for (h = heaps; h; h = h->next)
+	if ((char *)p >= arena(h) && (char *)p + sz < arena(h) + ARENA_SIZEOF(h))
+	    break;
+    unqueue_signals();
+
+    /* Do not free memory allocated in heap */
+    if (!h)
 	free(p);
 }
 
 /**/
+#endif
+
+/* this one is for strings (and only strings, real strings, real C strings,
+   those that have a zero byte at the end) */
+
+/**/
 mod_export void
 zsfree(char *p)
 {
     if (p)
-	free(p);
+	zfree(p, strlen(p) + 1);
 }
-
-/**/
-#endif

[-- Attachment #2: Type: application/pgp-signature, Size: 191 bytes --]

[PATCH] Re: dirstack history: loving zsh, crashing zsh...

[Andrey Borzenkov]

[-- Attachment #1.1: Type: text/plain, Size: 1659 bytes --]

On Saturday 04 March 2006 11:04, Andrey Borzenkov wrote:
> [moved to workers]
>
> On Thursday 02 March 2006 20:52, Francisco Borges wrote:
> > % typeset -U dirstack
> >
> > and the shell crashed.
>
> The problem is rather non-trivial. dirsgetfn returns array built on-the-fly
> in heap, while typeset -U calls uniqarray() that tries to zfree array
> elements. There are at least two problems here:
>
> - typeset -U is not prepared to deal with "pseudo" parameters at all. It
> assumes a->getfn() returns pointer to real parameter value. So it would
> have not worked for dirstack anyway
>
> - I was about to change typeset -U to pm->gsu.a->setfn(pm,
> pm->gsu.a->getfn(pm)) (basically doing foo=($foo)) and adding uniqarray
> call to dirssetfn() when I realized that it would not help at all in this
> case as dirssetfn() tries to free passed value too; so it would have
> crashed just the same.
>
> Apparently to solve it in general we need one of
>
> - per-parameter type ->uniq function (is it an overkill?) Possibly
> generalized to per-parameter ->setflags function.
>
> - some way to know if passed pointer was allocated from heap or not. I
> guess it should be possible; something like isheap(p)?
>

Assuming the issue with freeing heap memory is resolved, the patch adds 
support for -U to dirstack. It also adds framework for adding uniqueness 
support to any parameter by changing typeset to simply do equiv. of 
'foo=($foo)'. It also uncovered one case of using free() instead of zfree(); 
assuming previous patch is accepted it is necessary to audit code and replace 
all plain free() with zfree().

-andrey

[-- Attachment #1.2: dirstack_-U_support.patch --]
[-- Type: text/x-diff, Size: 2681 bytes --]

Index: Src/builtin.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/builtin.c,v
retrieving revision 1.151
diff -u -p -r1.151 builtin.c
--- Src/builtin.c	7 Nov 2005 09:37:34 -0000	1.151
+++ Src/builtin.c	4 Mar 2006 09:19:18 -0000
@@ -1920,24 +1920,17 @@ typeset_single(char *cname, char *pname,
 	    zerrnam(cname, "%s: restricted", pname, 0);
 	    return pm;
 	}
+	pm->flags = (pm->flags | (on & ~PM_READONLY)) & ~(off | PM_UNSET);
 	if ((on & PM_UNIQUE) && !(pm->flags & PM_READONLY & ~off)) {
 	    Param apm;
-	    char **x;
-	    if (PM_TYPE(pm->flags) == PM_ARRAY) {
-		x = (*pm->gsu.a->getfn)(pm);
-		uniqarray(x);
-		if (pm->ename && x)
-		    arrfixenv(pm->ename, x);
-	    } else if (PM_TYPE(pm->flags) == PM_SCALAR && pm->ename &&
-		       (apm =
-			(Param) paramtab->getnode(paramtab, pm->ename))) {
-		x = (*apm->gsu.a->getfn)(apm);
-		uniqarray(x);
-		if (x)
-		    arrfixenv(pm->nam, x);
-	    }
+
+	    if (PM_TYPE(pm->flags) == PM_ARRAY)
+		apm = pm;
+	    else if (PM_TYPE(pm->flags) == PM_SCALAR && pm->ename)
+		apm = (Param) paramtab->getnode(paramtab, pm->ename);
+	    if (apm)
+		apm->gsu.a->setfn(pm, apm->gsu.a->getfn(apm));
 	}
-	pm->flags = (pm->flags | (on & ~PM_READONLY)) & ~(off | PM_UNSET);
 	if (on & (PM_LEFT | PM_RIGHT_B | PM_RIGHT_Z)) {
 	    if (typeset_setwidth(cname, pm, ops, on, 0))
 		return NULL;
Index: Src/utils.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/utils.c,v
retrieving revision 1.118
diff -u -p -r1.118 utils.c
--- Src/utils.c	1 Mar 2006 14:50:52 -0000	1.118
+++ Src/utils.c	4 Mar 2006 09:19:21 -0000
@@ -2499,7 +2499,7 @@ freearray(char **s)
 
     while (*s)
 	zsfree(*s++);
-    free(t);
+    zfree(t, 0);
 }
 
 /**/
Index: Src/Modules/parameter.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Modules/parameter.c,v
retrieving revision 1.35
diff -u -p -r1.35 parameter.c
--- Src/Modules/parameter.c	10 Mar 2005 17:56:05 -0000	1.35
+++ Src/Modules/parameter.c	4 Mar 2006 09:19:21 -0000
@@ -929,15 +929,19 @@ scanpmmodules(UNUSED(HashTable ht), Scan
 
 /**/
 static void
-dirssetfn(UNUSED(Param pm), char **x)
+dirssetfn(Param pm, char **x)
 {
     char **ox = x;
 
     if (!incleanup) {
 	freelinklist(dirstack, freestr);
 	dirstack = znewlinklist();
-	while (x && *x)
-	    zaddlinknode(dirstack, ztrdup(*x++));
+	if (x) {
+	    if (pm->flags & PM_UNIQUE)
+		uniqarray(x);
+	    while (*x)
+		zaddlinknode(dirstack, ztrdup(*x++));
+	}
     }
     if (ox)
 	freearray(ox);

[-- Attachment #2: Type: application/pgp-signature, Size: 191 bytes --]

Re: [PATCH][RFC] check for heap memory in zfree()

[Bart Schaefer]

On Mar 4, 11:57am, Andrey Borzenkov wrote:
} 
} I did not receive my previous mail so I am not sure if it was ever 
} delivered ...

I don't recall seeing it but my mail was messed up for a while by a
bad interaction between a new /etc/hosts and an old /etc/hosts.allow.

} > The problem is rather non-trivial. dirsgetfn returns array built
} > on-the-fly in heap, while typeset -U calls uniqarray() that tries
} > to zfree array elements.

Peter's patch in 22318 fixes this by always copying the array in a
PM_ARRAY parameter before uniquifying it.  That conflicts with your
builtin.c hunk in 22320, which has the same effect except generalized
to all parameters.

I'm not entirely happy with either of these because both needlessly
duplicate memory in the case where the array is already free-able.
It seems as if it should be possible for "typeset -U" to be made more
efficient than assignment-by-copy.

Skipping ahead:

} OK attached is patch that checks if memory has been allocated from heap. 
} Comments on whether it makes sense?

I don't like this, either.  The free() operation should be very fast;
a scan for whether every pointer we might free is actually on the heap
is counter-productive.  And yes, it would mask other bugs.

People are already complaining that multibyte support has made zsh
significantly slower, let's not pile on still more overhead.

I suggest a compromise approach:  Add a function to test whether a
pointer is in one of the heaps, and when a caller is not certain about
the allocation of the memory it is about to free(), it can guard with
the test function.

In this specific case it's uniqarray() that is doing the unsafe freeing,
so that's where the call to the test function would go.  I think it's
safe to a assume that an array won't contain a mix of permanent and
heap memory, so we only need to make one call to the test.

} > There are at least two problems here:

Actually there are three, the last of which has nothing to do with the
crash: pushd/popd modify the internal dirstack linked-list directly,
so $dirstack does not remain unique.  Further, $PWD is never placed in
the directory stack until pushd, so the output of "dirs" is not unique
when the current directory is the same as one elsewhere in the stack.

Maybe someone can remind me why it's up to the parameter set-function
to free its argument?  That seems completely inside-out to me.

} > Apparently to solve it in general we need one of
} >
} > - per-parameter type ->uniq function (is it an overkill?) Possibly
} > generalized to per-parameter ->setflags function.

This does appear to be necessary in order to fix the third problem.  In
essence, "typeset -U dirstack" should execute "setopt pushdignoredups",
and nothing less is going to produce the desired effect.

Since it's probably a bad thing to have "typeset" produce side-effects
on "setopt", it might be more effective to enforce that -U does not
apply to dirstack.  All the other parameter module arrays are read-only,
but we'd still need some PM_ flag to handle this case in general.  Is
it reasonable to treat PM_REMOVABLE as an indication that the array is
constructed on the fly and hence can't be made unique?

I notice that there's no warning printed for typeset -U on a read-only
or non-array parameter, but there is a warning for -U on a restricted
parameter when the RESTRICTED option is set.  Isn't that inconsistent?

} > - some way to know if passed pointer was allocated from heap or not. I
} > guess it should be possible; something like isheap(p)?

The patch below adds zheapptr(p), which returns p if it is on the heap
or NULL otherwise.  This seemed more general than a simple boolean, but
it's not used for anything but boolean tests in the patch, which thereby
fixes uniqarray().

This patch also partly reverts 22318, opting to call the array set fn
after uniqarray() only for PM_SPECIAL parameters.  This keeps $dirstack
working the way it did after 22318, but does not fix problem #3.


Index: Src/builtin.c
===================================================================
RCS file: /extra/cvsroot/zsh/zsh-4.0/Src/builtin.c,v
retrieving revision 1.36
diff -u -r1.36 builtin.c
--- Src/builtin.c	4 Mar 2006 09:26:06 -0000	1.36
+++ Src/builtin.c	5 Mar 2006 08:59:00 -0000
@@ -1924,10 +1924,11 @@
 	    Param apm;
 	    char **x;
 	    if (PM_TYPE(pm->flags) == PM_ARRAY) {
-		x = zarrdup((*pm->gsu.a->getfn)(pm));
+		x = (*pm->gsu.a->getfn)(pm);
 		uniqarray(x);
-		pm->gsu.a->setfn(pm, x);
-		if (pm->ename && x)
+		if (pm->flags & PM_SPECIAL)
+		    (*pm->gsu.a->setfn)(pm, zarrdup(x));
+		else if (pm->ename && x)
 		    arrfixenv(pm->ename, x);
 	    } else if (PM_TYPE(pm->flags) == PM_SCALAR && pm->ename &&
 		       (apm =
Index: Src/mem.c
===================================================================
RCS file: /extra/cvsroot/zsh/zsh-4.0/Src/mem.c,v
retrieving revision 1.6
diff -u -r1.6 mem.c
--- Src/mem.c	14 Aug 2004 05:01:23 -0000	1.6
+++ Src/mem.c	5 Mar 2006 05:12:11 -0000
@@ -329,6 +329,21 @@
 }
 #endif
 
+/* check whether a pointer is within a memory pool */
+
+/**/
+mod_export void *
+zheapptr(void *p)
+{
+    Heap h;
+    queue_signals();
+    for (h = heaps; h; h = h->next)
+	if ((char *)p >= arena(h) &&
+	    (char *)p + H_ISIZE < arena(h) + ARENA_SIZEOF(h))
+	    break;
+    unqueue_signals();
+    return (h ? p : 0);
+}
 
 /* allocate memory from the current memory pool */
 
Index: Src/params.c
===================================================================
RCS file: /extra/cvsroot/zsh/zsh-4.0/Src/params.c,v
retrieving revision 1.34
diff -u -r1.34 params.c
--- Src/params.c	4 Mar 2006 09:26:06 -0000	1.34
+++ Src/params.c	5 Mar 2006 08:58:26 -0000
@@ -2820,11 +2820,11 @@
 	*dptr->arrptr = sepsplit(x, sepbuf, 0, 0);
 	if (pm->flags & PM_UNIQUE)
 	    uniqarray(*dptr->arrptr);
+	zsfree(x);
     } else
 	*dptr->arrptr = NULL;
     if (pm->ename)
 	arrfixenv(pm->nam, *dptr->arrptr);
-    zsfree(x);
 }
 
 /**/
@@ -2847,17 +2847,16 @@
 }
 
 /**/
-void
-uniqarray(char **x)
+static void
+arrayuniq(char **x, int freeok)
 {
     char **t, **p = x;
 
-    if (!x || !*x)
-	return;
     while (*++p)
 	for (t = x; t < p; t++)
 	    if (!strcmp(*p, *t)) {
-		zsfree(*p);
+		if (freeok)
+		    zsfree(*p);
 		for (t = p--; (*t = t[1]) != NULL; t++);
 		break;
 	    }
@@ -2865,18 +2864,20 @@
 
 /**/
 void
-zhuniqarray(char **x)
+uniqarray(char **x)
 {
-    char **t, **p = x;
+    if (!x || !*x)
+	return;
+    arrayuniq(x, !zheapptr(*x));
+}
 
+/**/
+void
+zhuniqarray(char **x)
+{
     if (!x || !*x)
 	return;
-    while (*++p)
-	for (t = x; t < p; t++)
-	    if (!strcmp(*p, *t)) {
-		for (t = p--; (*t = t[1]) != NULL; t++);
-		break;
-	    }
+    arrayuniq(x, 0);
 }
 
 /* Function to get value of special parameter `#' and `ARGC' */

Re: [PATCH][RFC] check for heap memory in zfree()

[Peter Stephenson]

Bart Schaefer wrote:
> I'm not entirely happy with either of these because both needlessly
> duplicate memory in the case where the array is already free-able.
> It seems as if it should be possible for "typeset -U" to be made more
> efficient than assignment-by-copy.
>...
> Maybe someone can remind me why it's up to the parameter set-function
> to free its argument?  That seems completely inside-out to me.

This second is the nub of the problem.  The API (if that isn't an
overgrand way of putting it in this case) requires the value to be
assigned permanently.  For normal parameters this is typically more
efficient (I presume; I haven't followed it through to make sure) since
there's no additional copy; it's just assigned to the array variable and
the old value is freed.  In this case we are doing something slightly
suspicious to make a feature implemented rather differently behave like
a parameter.

Later:
> } OR you guys are now going to say: "Don't you know you're not supposed
> } to use typeset with dirstack!!"
> 
> You aren't, but the shell isn't supposed to crash, either.

Why not?  If you weren't supposed to do that kind of thing, dirstack
wouldn't be writeable.  Since it is, this needs to be handled
transparently.  If it quacks like a parameter and waddles like a
parameter, a user should assume it swims on water like a parameter (er,
as it were).

It seems to me that behind both of these is the tension between the
ability to make a feature look like a parameter and efficiency of
implementation for normal parameters.  I don't see how we can do both,
except with lots of ad hoc testing for specialness, which fixes the
problem at the expense of yet more complexity.  That is at least the
standard zsh way out.

-- 
Peter Stephenson <p.w.stephenson@ntlworld.com>
Web page still at http://www.pwstephenson.fsnet.co.uk/

Re: [PATCH][RFC] check for heap memory in zfree()

[Bart Schaefer]

On Mar 5,  5:23pm, Peter Stephenson wrote:
} Subject: Re: [PATCH][RFC] check for heap memory in zfree()
}
} Bart Schaefer wrote:
} > Maybe someone can remind me why it's up to the parameter set-function
} > to free its argument?  That seems completely inside-out to me.
} 
} For normal parameters this is typically more efficient (I presume; I
} haven't followed it through to make sure) since there's no additional
} copy; it's just assigned to the array variable and the old value
} is freed.

Knowing a bit about how PF thinks, that's probably the right answer.

Any objections to my committing my patch?  With one additional tweak
to call zheapptr() before zarrdup() in the builtin.c hunk.
 
} Later:
} > } OR you guys are now going to say: "Don't you know you're not
} > } supposed to use typeset with dirstack!!"
} >
} > You aren't, but the shell isn't supposed to crash, either.
} 
} Why not?

schaefer[514] typeset -T DIRSTACK dirstack
typeset: dirstack: can't change type of a special parameter

IMO a unique array is a distinct type from an ordinary array.

} If you weren't supposed to do that kind of thing, dirstack wouldn't
} be writeable.  Since it is, this needs to be handled transparently.
} If it quacks like a parameter and waddles like a parameter, a user
} should assume it swims on water like a parameter (er, as it were).

Some of our quacking and waddling parameters are already dog-paddling.
For example, although you can (without getting warnings) set the -LRZ
options on any array, they don't have any effect except to make the
array show up in "typeset -LRZ" output.

} It seems to me that behind both of these is the tension between the
} ability to make a feature look like a parameter and efficiency of
} implementation for normal parameters.

I think you're only half right.  Efficiency isn't the problem when it
comes to having an internal construct like the dirstack linked list
made visible via an array parameter -- the problem is that there's no
way for the other code that manipulates the structure to know that
the parameter exists and has its own value rules.  The way to fix
that is to require that the parameter's rules conform to the internal
structure it represents, not the other way around.

Re: [PATCH][RFC] check for heap memory in zfree()

[Peter Stephenson]

Bart Schaefer wrote:
> Any objections to my committing my patch?  With one additional tweak
> to call zheapptr() before zarrdup() in the builtin.c hunk.

I think it's OK.

> schaefer[514] typeset -T DIRSTACK dirstack
> typeset: dirstack: can't change type of a special parameter
> 
> IMO a unique array is a distinct type from an ordinary array.

I'm not convinced about that.  I think it's just a tidying up operation
performed on the value.

> Some of our quacking and waddling parameters are already dog-paddling.
> For example, although you can (without getting warnings) set the -LRZ
> options on any array, they don't have any effect except to make the
> array show up in "typeset -LRZ" output.

That's a bug, probably, although it might need care fixing (does the
flag apply if the array is about to be joined?)

> The way to fix
> that is to require that the parameter's rules conform to the internal
> structure it represents, not the other way around.

Yes, but I think the correspondence can sometimes be made more logical.
It doesn't make sense to have dirstack an integer, but it does makes
sense to have it contain unique elements.

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR PLC, Churchill House, Cambridge Business Park, Cowley Road
Cambridge, CB4 0WZ, UK                          Tel: +44 (0)1223 692070


To access the latest news from CSR copy this link into a web browser:  http://www.csr.com/email_sig.php

Re: [PATCH][RFC] check for heap memory in zfree()

[Bart Schaefer]

On Mar 6, 10:32am, Peter Stephenson wrote:
}
} Bart Schaefer wrote:
} > IMO a unique array is a distinct type from an ordinary array.
} 
} I'm not convinced about that.  I think it's just a tidying up operation
} performed on the value.

If it only happened on output, like -LRZ, I'd agree with you.  But then
it would be worse than useless for dirstack.

} > For example, although you can (without getting warnings) set the -LRZ
} > options on any array, they don't have any effect except to make the
} > array show up in "typeset -LRZ" output.
} 
} That's a bug, probably, although it might need care fixing (does the
} flag apply if the array is about to be joined?)

I'd be tempted to say they apply when joining with $arr[@] but not with
$arr[*], but -Z gives me pause.  I guess I think -LR should work like
${(l:N:)...} and ${(r:N:)...}, which is where the [@] [*] distinction
comes from.  I wish (l) were for lower-case and (r) for match-rest so
we could have (L:N:) (R:N:) and add (Z:N:), but it's years too late now.

} It doesn't make sense to have dirstack an integer, but it does makes
} sense to have it contain unique elements.

That could be made to "work" for dirstack by adopting something like
Andrey's 22320, where the set-fn is not called until after the new
flags are in place.  dirssetfn() could then check for PM_UNIQUE and
frob PUSHD_IGNORE_DUPS to match.

I think that would be even more broken, though.  The number of possible
bad interactions doubles -- people would be confused about why their
change to setopt reverts whenever they assign to dirstack, etc.

--