xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/10/91)
Hi, sorry to butt in on the wrong side of the Amiga/Atari free fire zone, but I need a little help from someone familiar with the Atari version of Lattice C. I'm trying to bring up a version of the Boyer/Moore sublinear time string search algorithm on a BSD 4.3 Unix box. Unfortunately, from my point of view, the sources I have are an Atari ST port that was done without #ifdef conditionalizing, and I'm having trouble understanding a small piece of Lattice C code, specifically, what some calls to Malloc are doing. My (Amiga) version of Lattice C doesn't include the "Malloc" call, so my own docs are useless. The code looks like this: |=| #include <stdio.h> |=| #include <osbind.h> |=| #include "bm.h" |=| #include "extern.h" |=| |=| static void loinit(); |=| static int loread(); |=| |=| Execute(DescVec, NPats, TextFile, Buffer, inbufsiz) |=| { |=| ... |=| /* initialize */ |=| loinit(); |=| ... |=| } /* Execute */ |=| |=| static char *lobuf, *lopos; |=| static int lobread, loeof, lbsiz; |=| |=| static void loinit() |=| { |=| int newsiz; |=| |=| if (lobuf == (char *)0) { (1) |=| lbsiz = Malloc(-1); (2) |=| while (newsiz = lbsiz & (lbsiz-1)) { |=| lbsiz = newsiz; |=| } (3) |=| lobuf = (char *)Malloc(lbsiz); (4) |=| if (lobuf == (char *)-1) { |=| fprintf(stderr,"bm: memory allocation failed\n"); |=| exit(1); |=| } |=| } |=| lopos = lobuf; |=| lobread = 0; |=| loeof = 0; |=| } Elsewhere, _mneed is set to 30000 bytes, which, I understand, establishes a minimum heap space available by setting a global for the compiler. Pretty obviously, after you stare at the (rather clever) loop at (2) until your eyes cross a bit, what's going on is an allocation of a block sized a power of 2 the largest contained in the value returned to lbsize by "Malloc" at (1). Questions: a) Is the "Malloc" call at (1) getting the largest available block in the operating-system-maintained free list? b) If not, what's going on with the "-1" parameter (and is it being promoted to a long integer behind the scenes, while I'm asking)? c) Could the call at (1) return a value _larger_ than "_mneed" is set? d) I'm used to seeing (lower case) "malloc" return a zero (== null pointer) when allocation of the requested size isn't possible. Why is the test of the value returned by "Malloc" at (3) done against a pointer cast of "-1" at (4) instead? e) What would a zero return have implied that a "-1" return doesn't from "Malloc"? f) What exactly is the "-1" return telling me about an allocation failure? Email responses only, please; I really try to keep out of newsgroups where I have no business, since I tend to answer 10% of what I read otherwise. ;-) If this is something everyone but me reading this doesn't already understand, email a request for a summary of responses, and I'll gladly post one back here. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/12/91)
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: Just a note back to say thanks to the already half dozen folks who responded with useful answers, and to anyone else whose response is in the pipeline. Here's a quick summary of the answers. > Hi, sorry to butt in on the wrong side of the Amiga/Atari free fire > zone, but I need a little help from someone familiar with the Atari > version of Lattice C. ... > The code looks like this: ... |=| if (lobuf == (char *)0) { (1) |=| lbsiz = Malloc(-1); (2) |=| while (newsiz = lbsiz & (lbsiz-1)) { |=| lbsiz = newsiz; |=| } (3) |=| lobuf = (char *)Malloc(lbsiz); (4) |=| if (lobuf == (char *)-1) { |=| fprintf(stderr,"bm: memory allocation failed\n"); |=| exit(1); |=| } |=| } > Elsewhere, _mneed is set to 30000 bytes, which, I understand, > establishes a minimum heap space available by setting a global for the > compiler. > Pretty obviously, after you stare at the (rather clever) loop at (2) > until your eyes cross a bit, what's going on is an allocation of a > block sized a power of 2 the largest contained in the value returned > to lbsize by "Malloc" at (1). I got told that what this loop was doing still wasn't clear, even _with_ staring crosseyed at it, so here's an example: Say the value returned to lbsize is 0010001001 binary; then what the repeated minus 1's and bitwise ands do is: 0010001001 a -1 0010001000 b a & b = 0010001000 c -1 0010000111 d c & d = 0010000000 e <---- This is the last one saved into lbsiz... -1 0001111111 f e & f = 0000000000 g <---- ... because this one is "false", so the while loop insides don't get executed for it. i.e., they "eat" the less significant "set" ("1") bits off from the right; but since you save the last non-"false" value after an &= step, you have in lbsiz the largest power of two that fits in the original (largest available hunk) size returned by the Malloc(-1L). Like I said, you just have to cross your eyes right to visualize what's going on. > Questions: > a) Is the "Malloc" call at (1) getting the largest available block in > the operating-system-maintained free list? Answer: it is returning the _size_ of the largest available block, not a pointer to such a block. [I _hate_ it when a call can return values in type conflict depending on the parameters; miserable software engineering design; it should be two separately named routines returning the pointer versus the long integer values, even though pointers happen to be implemented _on_ _this_ _machine_ as long integers.] > b) If not, what's going on with the "-1" parameter (and is it being > promoted to a long integer behind the scenes, while I'm asking)? Answer: it not exactly being "promoted" because the Lattice compiler is using 32 bit integers as the native default; by me (and by my correspondent) that makes the "1" a portability problem and thus a coding error; it should have been "1L". c) Could the call at (1) return a value _larger_ than "_mneed" is set? Answer: yes indeed, it will return the size of the largest free block, which makes the call a system killer on a virtual memory system (and pretty unfriendly on _any_ multitasking system); on a Unix box this is typically going to grab 8 megs of memory from the virtual memory swap area; _way_ overkill when the setting for _mneed indicates that 30K would do fine. Another portability problem. > d) I'm used to seeing (lower case) "malloc" return a zero (== null > pointer) when allocation of the requested size isn't possible. Why is > the test of the value returned by "Malloc" at (3) done against a > pointer cast of "-1" at (4) instead? > e) What would a zero return have implied that a "-1" return doesn't > from "Malloc"? > f) What exactly is the "-1" return telling me about an allocation > failure? Answer (to d, e, and f): it's a coding bug and should have tested against "0L" or null; like "malloc", "Malloc" gives back a null, not a (char *)(-1), on allocation failure. [This still is a design problem with "Malloc", though, because "zero" (there are no free blocks) is a legitimate, non-failure answer to "Malloc(-1L)", though in practice there isn't much difference in what you'd do in response to "no storage free" versus "attempting to get storage failed" in any case, but the response should _not_ confound the two answers; more bad software engineering.] > Email responses only, please; I really try to keep out of newsgroups > where I have no business, since I tend to answer 10% of what I read > otherwise. I'll go away again now. ;-) > If this is something everyone but me reading this doesn't already > understand, email a request for a summary of responses, and I'll > gladly post one back here. Well, no one asked, but the responses were useful enough I thought I'd post one anyway, since there were some good lessons to be learned. Thanks again for all the help. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>