mwm@violet.berkeley.edu.UUCP (04/13/87)
Somewhere along the way, I picked up a program called frags. It
reports the number of free blocks of size 2^(n-1) to (2^n)-1 for n up
to 19 or so (blocks of max size 512K-1). Since it's easy to have
blocks bigger than 512K, I rewrote it to handle n up to 24 (blocks of
16Meg). Those of you with 68020's can rewrite it to handle n up to 32
if you wish. Since the result is also 300 bytes smaller than the
original, I'm happily replacing the old one everywhere.
I tweaked it a little on the way through, so blocks smaller than any
possible (8 is the smallest possible), including zero-sized blocks,
are handled (just to prevent them from raping things should they occur
because of bugs elsewhere. I also deleted the header so that the
output can be fed to filters. Oughta delete the `:' also, but...
This also represents my first attempt at Knuth's "literate
programming." Need to go read the references to get it right, but the
results speak for themselves (at length).
<mike
------------------------------ cut here ------------------------------
/*
* frags - a replacement for the frags command that will work on more than
* 512K of memory. In fact, I went ahead and set things up for 16Meg.
*
* Note - I'm trying Knuths "literate programming," and attempting to explain
* what's going on to some unknown audience. He claims this produces fewer
* bugs. If nothing else, it produces more comments.
*
* I'd like to know what others think of the result. You can send (electronic)
* mail to me as mwm@berkeley.edu, or ucbvax!mwm.
*
* Copyright (c) 1987, Mike Meyer
* All Rights Reserved
*
* This code may be freely redistributed, so long as the source is made
* available, and this notice is left in. You can even sell copies if you
* want to, if you make the source available complete with this notice.
*/
#include <exec/types.h>
#include <exec/exec.h>
#include <exec/execbase.h>
/*
* Generic comment on printing - all we're doing is pushing numbers out
* on standard output, so we don't need the power (and hence size) of
* printf. We pass the size & count to Print_Count, which will do all
* the work. The original printfs have been left in place for reference.
* Print_Count doesn't return anything, so we declare it void.
*/
void Print_Count(long, long) ;
/*
* Since we need to convert two longs to ASCII, we'll turn that into a
* subroutine that does all the work. It returns the same thing as
* Print_Count, and so has the same type.
*/
void Long_To_ASCII(long, char *, int) ;
/*
* We don't use the arguments, so use _main instead of main. Also, we're
* not going to return anything, so make _main() a void function.
*/
void
_main() {
/*
* There is a list of headers, each of which describes memory of some
* single type. Each header contains a pointer to the list of chunks
* of memory that it tracks. hdr will be used to point to each element
* in list of headers in turn.
*/
register struct MemHeader *hdr ;
/*
* Each header has a list of chunks of memory associated with it.
* chunk will be used to point to each chunk of every header.
*/
register struct MemChunk *chunk ;
/*
* Each chunk contains the size of the chunk, and a pointer to the
* next chunk. This size includes the size & next pointer for that
* chunk, but we're going to ignore that. We copy the size to a
* register variable for speed.
*/
register long size ;
/*
* SysBase is a pointer to lots of interesting data. For this
* program, we're going to get the pointer to the first memory
* header structure.
*/
extern struct ExecBase *SysBase ;
/*
* The 680[01]0 has a 24 bit address space. For each bit, we're
* going to count the number of chunks whose size has that bit
* as it's high-order bit. Hence, 24 slots in the array. However,
* we're going to have an extra slot for zero-sized chunks, which
* shouldn't occur, so the program won't die horribly if they
* occur. Thus, we have 25 slots. Chunks of size 2^(N-1) to (2^N)-1
* will be counted in slot N. Also, since there can be more than 16
* bits of 8-byte chunks, we need longs to hold the counter.
* Finally, declare it static so that it will be zero'ed by the
* loader.
*/
static long Chunk_Count[25] ;
/*
* Given an array, we really need something to index it with. Being
* an old FORTRAN hacker, I tend to favor i.
*/
register short i ;
/*
* We need to prevent other tasks from changing the memory list
* while we're walking it. Forbid() turns off task switching, so
* that we are the only task running.
*/
Forbid() ;
/*
* There is a standard list structure in AmigaDOS. SysBase contains
* a pointer to the list header for the list of memory headers
* (MemList), and lh_Head is the first member of that list.
*/
hdr = (struct MemHeader *) SysBase -> MemList . lh_Head ;
/*
* Each element in an AmigaDOS list starts with a standard Node
* structure, in this case called mh_Node. ln_Succ is the link to
* the successor node in this list, and is part of the standard node
* structure. Standard lists are a circular doubly-linked, with a
* distinguished header/trailer node. This node is distinguished by
* having a zero (false) successor. So we stop walking the list when
* mh_Node . ln_Succ of hdr is false.
*/
while (hdr -> mh_Node . ln_Succ) {
/*
* Chunks are a singly linked list, holding the length of the
* chunk and a pointer to the next chunk. The end of the
* chunk is denoted by a false pointer. Since the trailer is
* not distinguished, we check for chunk itself to be zero,
* not for it's successor to be false.
*
* I suspect that a standard AmigaDOS list wasn't used as that
* would have made the smallest possible memory chunk larger.
*/
for (chunk = hdr -> mh_First; chunk; chunk = chunk -> mc_Next) {
/*
* The size of the chunk is called mc_Bytes. Save it
* in a register for speed.
*/
size = chunk -> mc_Bytes ;
/*
* Now, count how many times you can shift size right
* before it becomes zero. i right shifts before size
* goes to zero will mean that size was between 2^(i-1)
* and (2^i)-1 at the start of the loop (unless i is
* zero, which means that size was 0), so we want to
* increment the Chunk_Count slot i. The special case
* for a zero-size chunk just falls out.
*/
for (i = 0; size; i += 1) size >>= 1 ;
Chunk_Count[i] += 1 ;
}
/*
* Since the successor is non-zero, we need to switch to it,
* and then go over the next headers list of chunks.
*/
hdr = (struct MemHeader *) hdr -> mh_Node . ln_Succ ;
}
/*
* We're through playing with the memory list, so we use Permit()
* to turn task switching back on. This is called "being polite."
*/
Permit() ;
/*
* The zero-length chunks don't fit the standard pattern, so
* print their count first. Use the same existence test as the
* standard loop, though.
*/
if (Chunk_Count[0])
Print_Count((long) 0, Chunk_Count[0]) ;
/*
printf("%8ld: %8d\n", (long) 0, Chunk_Count[0]) ;
*/
/*
* Finally, we want to print the results of all this. So, we
* let the index (i) iterate over the slots in the chunk counter,
* from 1 to 23. Slot 0 has already been handled.
*/
for (i = 1; i <= 23; i += 1)
/*
* If Chunk_Count for this slot is non-zero (true), we
* print it. Otherwise, we skip it.
*/
if (Chunk_Count[i])
/*
* Chunk_Count[i] contains a count of the number of
* chunks of size 2^(i-1) to 2^(i-1). So print 2^(i-1)
* and the count for chunks in that size range. Once
* again, we need more than 16 bits for possible
* sizes, so print it as a long, and cast the size
* argument to long.
*/
Print_Count(((long) 1) << (i - 1), Chunk_Count[i]) ;
/*
printf("%8ld: %8d\n",
((long) 1) << (i - 1), Chunk_Count[i]) ;
*/
}
/*
* Print_Count - print the pair of longs in fields of 8 spaces, seperated
* by a `:' and terminated by a newline.
*/
void
Print_Count(first, second)
register long first, second;
{
/*
* Each long goes into a field 8 wide. We'll need that number 8
* in a number of places, so give it a nice name.
*/
#define OUTPUT_FIELD_SIZE 8
/*
* The full field to be printed has two fields, plus a colon and
* a newline. We need that width in a few places also, so we give
* it a name too.
*/
#define OUTPUT_SIZE ((2 * OUTPUT_FIELD_SIZE) + 1 + 1)
/*
* Finally, we need a place to put the output string. So we declare
* a character array of the appropriate size.
*/
char buffer[OUTPUT_SIZE] ;
/*
* Let's do the easy part first, and put in the colon and the
* newline. The array is zero-based, so OUTPUT_FIELD_SIZE is
* the correct index for the colon (the first character after
* the first output field), and OUTPUT_SIZE is one greater than
* the index of the last character, so we use OUTPUT_SIZE - 1.
*/
buffer[OUTPUT_FIELD_SIZE] = ':' ;
buffer[OUTPUT_SIZE - 1] = '\n' ;
/*
* Now, we call Long_To_ASCII, which expects a pointer to the
* end of the field it's to fill, and the length of the field
* it's to fill. It'll put the number in place, and fill the
* rest of the field with spaces. See the previous comment for
* a discussion of the indices used.
*/
Long_To_ASCII(first, &buffer[OUTPUT_FIELD_SIZE - 1],
OUTPUT_FIELD_SIZE) ;
Long_To_ASCII(second, &buffer[OUTPUT_SIZE - 2],
OUTPUT_FIELD_SIZE) ;
/*
* Finally, print the result. Just call Write() with the output
* buffer and it's length, telling it to use the Output() stream.
*/
Write(Output(), buffer, OUTPUT_SIZE) ;
}
/*
* Long_To_ASCII - convert the first argument into an ASCII string ending
* at the second argument, and fill out the field to the third argument
* with spaces.
*/
void
Long_To_ASCII(in, out, length)
register long in;
register char *out;
register int length;
{
/*
* If in is zero, we just put in a single '0'.
*/
if (in == 0) {
*(out--) = '0' ;
/*
* We've put in a digit, so reduce the length by 1.
*/
length -= 1 ;
}
/*
* Otherwise, we need to strip the digits off of in and put them
* in the array.
*/
else
while (in != 0) {
/*
* To prevent overflows, we check to make sure
* that there's space for this digit. If not,
* we just return, with no comment.
*/
if (length == 0) return ;
/*
* The current low-order digit is merely in rem 10,
* which, if we add it to '0', will be the ASCII
* representation of that low-order digit.
*/
*(out--) = (in % 10) + '0' ;
/*
* Once again, we've put in a digit, so we reduce
* length.
*/
length -= 1 ;
/*
* Since we've got in's low order digit, we want
* the next lower order digit to be in place for
* the next loop iteration. This can be done by
* dividing in by 10.
*/
in /= 10 ;
}
/*
* Now, for however much length is left, we put a space in out,
* and nudge out to the next space.
*/
while (length-- != 0)
*(out--) = ' ' ;
}
/*
* To cut down on memory useage, we provide a stub for a routine pulled
* in by the default startup code in _main. This code cleans up
* dynamically allocated memory, which we don't need. So we flush the code
* here. By making this a smallcode, smalldata program, turning off stack
* checking (nothing recursive, and only three routines, so who needs it?),
* and adding this, I've reduced the size of frags to 1644 bytes. Since the
* original frags is 1964 bytes long, I'm happy. Just out of curiosity, I'd
* like to know how large a binary Manx 3.4 produces.
*/
void
MemCleanup() {}
--
Here's a song about absolutely nothing. Mike Meyer
It's not about me, not about anyone else, ucbvax!mwm
Not about love, not about being young. mwm@berkeley.edu
Not about anything else, either. mwm@ucbjade.BITNETkent@xanth.UUCP (04/15/87)
In article <3148@jade.BERKELEY.EDU> mwm@violet.berkeley.edu(Mike (My watch has windows) Meyer) writes: > * Note - I'm trying Knuths "literate programming," and attempting to explain > * what's going on to some unknown audience. He claims this produces fewer > * bugs. If nothing else, it produces more comments. > * > * I'd like to know what others think of the result. You can send (electronic) > * mail to me as mwm@berkeley.edu, or ucbvax!mwm. The old leadership axiom (me, lead somebody this much better than I am? Not a chance) says praise in public, reprimand in private. Here goes. I absolutely love your code, Mike. I wish every piece of C code I had ever read, read like your "frags" program. Code like this is a good tutorial for the beginning programmer, eases program maintenance manyfold, is a joy to behold, and is the mark of a true professional. You just moved Knuth up a few notches closer to the top of my hero list, and got yourself a spot, as well. I sure hope that _lots_ of programmers see and follow your example. Well done! Kent. -- The Contradictor Member HUP (Happily Unemployed Programmers) // Also // A Back at ODU to learn how to program better (after 25 years!) \\ // Happy \// Amigan! UUCP : kent@xanth.UUCP or ...{sun,cbosgd,harvard}!xanth!kent CSNET : kent@odu.csnet ARPA : kent@xanth.cs.odu.edu Voice : (804) 587-7760 USnail: P.O. Box 1559, Norfolk, Va 23501-1559 Copyright 1987 Kent Paul Dolan. How about if we keep the human All Rights Reserved. Author grants free race around long enough to see retransmission rights, recursively only. a bit more of the universe?
rico@oscvax.UUCP (04/15/87)
In article <3148@jade.BERKELEY.EDU> mwm@violet.berkeley.edu(Mike (My watch has windows) Meyer) writes: > [Edited: a whole bunch of source ] > >/* > * To cut down on memory useage, we provide a stub for a routine pulled > * in by the default startup code in _main. This code cleans up > * dynamically allocated memory, which we don't need. So we flush the code > * here. By making this a smallcode, smalldata program, turning off stack > * checking (nothing recursive, and only three routines, so who needs it?), > * and adding this, I've reduced the size of frags to 1644 bytes. Since the > * original frags is 1964 bytes long, I'm happy. Just out of curiosity, I'd > * like to know how large a binary Manx 3.4 produces. > */ >void >MemCleanup() {} Manx 3.4, using just the +L option (force 32 bit integers) compiled the code just fine (once I removed the ANSI-style argument type declarations) and produced a 796 byte binary. -Rico -- [NSA food: terrorist, cryptography, DES, drugs, CIA, secret, decode] [CSIS food: supermailbox, tuna, fiberglass coffins, Mirabel, microfiche] [Cat food: Nine Lives, Cat Chow, Meow Mix, Crave]
walton@tybalt.caltech.edu (Steve Walton) (04/16/87)
In article <3148@jade.BERKELEY.EDU> mwm@violet.berkeley.edu(Mike (My watch has windows) Meyer) writes (in the comments to his replacement frags program): >/* > * To cut down on memory useage, we provide a stub for a routine pulled > * in by the default startup code in _main. This code cleans up > * dynamically allocated memory, which we don't need. So we flush the code > * here. By making this a smallcode, smalldata program, turning off stack > * checking (nothing recursive, and only three routines, so who needs it?), > * and adding this, I've reduced the size of frags to 1644 bytes. Since the > * original frags is 1964 bytes long, I'm happy. Just out of curiosity, I'd > * like to know how large a binary Manx 3.4 produces. > */ Well, now, I made a couple of small changes in Mike's code. I removed the prototyping for Long_To_ASCII and Print_Count (since Manx doesn't support it), declared long Output() in Print_Count(), and cast OUTPUT_SIZE to (long) in Print_Count's call to Write(). Resulting executable was 796 bytes long, slightly less than half the size of the Lattice one. This was small code, small data, 16 bit ints. It worked, too, by the way :-> Steve Walton guest as walton@tybalt.caltech.edu
fwp@unccvax.UUCP (04/17/87)
Why do I get the following errors when I try to compile the frags replacement program? What symbol is it referring to? I am a novice at c, but this really doesn't make any sense to me. cc frags.c Aztec C68K 3.4a 2-3-87 (C) 1982-1987 by Manx Software Systems, Inc. register long first, second; ^ frags.c:192: ERROR 90: symbol redeclared: Print_Count register long in; ^ frags.c:247: ERROR 90: symbol redeclared: Long_To_ASCII 2 errors Any help would be greatly appreciated. Rick Pasotto
mwm@eris.UUCP (04/17/87)
In article <671@unccvax.UUCP> fwp@unccvax.UUCP (Rick Pasotto) writes: >Why do I get the following errors when I try to compile the frags >replacement program? What symbol is it referring to? I am a novice >at c, but this really doesn't make any sense to me. > >cc frags.c >Aztec C68K 3.4a 2-3-87 (C) 1982-1987 by Manx Software Systems, Inc. > register long first, second; ^^^^^ > ^ >frags.c:192: ERROR 90: symbol redeclared: Print_Count > register long in; > ^ >frags.c:247: ERROR 90: symbol redeclared: Long_To_ASCII >2 errors > >Any help would be greatly appreciated. > >Rick Pasotto Your problem is your compiler. There are two possible solutions: 1) Buy a compiler that understands function prototypes, and use it instead (1/2 :-). 2) Delete the two lines that look like bodyless function declarations: void Print_Count(long, long) ; and void Long_To_ASCII(long, char *, int) ; While you're at it, you'll need to add a line like so in about the same place: long Write(), Output() ; and cast the OUTPUT_SIZE argument of Write to a long. To Manx Users (and writers): Sorry about those prototypes, but they make the code more readable. As far as I'm concerned, readability takes precedence over portability. Hence, I use prototypes, void's and long names. You should make noises to have them added to the compiler! <mike -- Here's a song about absolutely nothing. Mike Meyer It's not about me, not about anyone else, ucbvax!mwm Not about love, not about being young. mwm@berkeley.edu Not about anything else, either. mwm@ucbjade.BITNET
vanam@pttesac.UUCP (Marnix van Ammers) (04/19/87)
In article <3204@jade.BERKELEY.EDU> mwm@eris.BERKELEY.EDU (Mike (My watch has windows) Meyer) writes: >In article <671@unccvax.UUCP> fwp@unccvax.UUCP (Rick Pasotto) writes: >>Why do I get the following errors when I try to compile the frags >Your problem is your compiler. There are two possible solutions: > >1) Buy a compiler that understands function prototypes, and use it > instead (1/2 :-). I had never heard of prototypes before. Don't recall reading about them in my (old) C books. But they sound like a good idea. I guess they show the types of arguments passed to a function as well as what the function returns. Maybe Manx will add prototypes to their Aztec-C compiler one day. In the meantime I guess Manx users can change void Long_To_ASCII(long, char *, int); to #ifndef AZTEC_C void Long_To_ASCII(long, char *, int); #else void Long_To_ASCII(); #endif or if that looks too messy, to void Long_To_ASCII(/* long, char *, int */); I really liked the heavy documentation in the frags program. I also like the small executable. Marnix -- Marnix (ain't unix!) A. van\ Ammers Work: (415) 545-8334 Home: (707) 644-9781 CEO: MAVANAMMERS:UNIX UUCP: {ihnp4|ptsfa}!pttesac!vanam CIS: 70027,70