Departments

We Have Mail

Dear Robert:

I was pleased to see Bob Withers' article on "Unnamed Pipes," and the example program ROUTEMSG, published in the July 1990 issue. This is the first public domain software I have seen for OS/2 and I think some points are worth noting:

Bob presented a clever program which achieves the rare status of being both technically innovative and genuinely useful. More on OS/2 please.

Yours faithfully,

Richard Howells
Farmarsh House, Cotmarsh,
Broad Town, Swindon,
SN4 7RA,
United Kingdom

I think your appraisal that "a few programmers are riding their bikes around the OS/2 API" is right on target. Our most recent surveys indicate that most programmers are not yet ready to take the OS/2 leap. As more working programmers begin to mount the learning curve, we'll run more OS/2 coverage. — rlw

Dear Mr. Ward,

Regarding David Grey Stahl's letter in the August 1990 issue of The C User's Journal, I would like to offer some information which might help clarify some things.

Unfortunately, I don't use MSC, but I did spend the better part of a day investigating how Turbo C handles its malloc() and free() routines. I went to the heart of the matter by single stepping through some malloc() and free() calls using Turbo Debugger. Perhaps Mr. Stahl or another MSC user could do the same with Code View.

The first thing to note is that each malloc() ed block of memory is immediately preceded by a bookkeeping header. In the small data memory models, this consists of a near pointer and an unsigned integer, for a total of four bytes. In the large data models, this is a far pointer and an unsigned long, for a total of eight bytes. The pointer points to the preceding contiguous block of memory, and the unsigned holds the size of the block, as well as a bit indicating whether the block is free or allocated.

In small data models, see Figure 1. These values must be addressable in the segment, so the maximum usable data in a segment is limited by the size.e of the overhead block. There is also another limitation. To ensure that a pointer returned by malloc() is aligned to hold any structure, as well as to make the whole memory allocation more efficient, memory is allocated in blocks of eight in small data models, and in blocks of 16 in large data models. From now on, I will talk about small data models, but the same holds true in large data models. Simply substitute the proper sizes.

A request for one byte is really a request for five bytes when the header is included. The next larger blocksize is eight, so you are returned a block of eight bytes. A request for two bytes (really six) also results in the allocation of an eight-byte block. A request for five bytes is really asking for nine bytes, resulting in the allocation of 16 bytes.

Since malloc() takes an argument of type size t, and size t is typedefed to unsigned int, the maximum requestable size is 65535 bytes. Out of a possible 65535 bytes, it is clear that seven bytes cannot be allocated (65535 == 8191 * 8 + 7). Also, out of the 65528 available bytes, we lose four to the header, bringing us to a grand total of 65524 usable data bytes. This number drops to 65512 in large data models (65535 = = 4095*16 + 15, so 65520 available, less eight bytes header overhead).

Unfortunately, requests for sizes in the limbo range above the maximum usable size but below 65535 can succeed, but are obviously not safe to use. The data starts four bytes into the segment, and trying to address the high bytes can lead to segment wrap-around — a very dangerous prospect, since writing to a wrapped address will surely destroy the header information, and the system will likely crash on the next malloc() or free().

The maintenance of the heap is actually very clever, while at the same time very simple. The runtime library has three pointers it uses to maintain the doubly-linked list of memory blocks: first, last, and rover. first points to the first allocated block, last points to the last allocated block, and rover points to the first freed block. I did say that the list was doubly-linked. The header contains a pointer to the previous block. But it also contains the size of the block. Knowing the address and the size of a structure, we can easily obtain the address of the memory which follows it by simply adding the base address and the size.

But what about the flag value? Well, if you recall that blocks are allocated in blocks of size 8, it should be clear that the three low-order bits of the size will not be used. Turbo C uses the low-order bit as a flag indicating whether the block is allocated or free. It simply sets the bit at allocation, and resets it to 0 when the block is freed. It masks off the bit to correctly calculate addresses. When malloc() receives a request the following happens:

1. If the size of the request, n, is 0, return NULL.

2. Determine the proper allocation size by adding 12 and anding off three low bits. for example, let n = 21 or 0x0015. Add 12, 0x0015 + 0x000C = 0x0021. And off low-order bits, 0x0021 & 0xFFF8 = 0x0020. So, we will need to get 32 bytes.

3. Attempt to allocate the memory. If rover is NULL, we simply see if we can increase the heap. If we can, we do so, and set the block's prev-pointer to last (the old heap top). Then we set last to point to the new heap top. If rover is not NULL, there are freed blocks to investigate. Starting at the block pointed to by rover, we walk the list of blocks until we find a free block large enough to hold the request. This block is divied up, and we use part of it while the rest goes back as free memory. If no freed blocks are large enough, we fall back and try to expand the heap as described above. The prev-pointers and size/flag bytes of all blocks involved are adjusted as necessary.

If after all this we cannot get the memory we return NULL, otherwise we return the address of the allocated block's data area.

A call to free() is a little simpler.

1. If we try to free NULL, simply return.

2. Mark the block as freed by resetting the flag bit.

3. If the block following this block is marked as freed, add its size to the size of the current block.

4. If the block preceding this block (via the prev-ptr in the header) is marked as freed, add the size of the current block to the preceding block.

5. If the resultant block is below the block pointed to by rover in the heap, make rover point to the resultant block.

In Turbo C there are memory models which have both near and far heaps, and the above is duplicated. That is, there is a doubly-linked list of block in the near heap, and a second, separate list of blocks in the far heap. Calls to malloc() result in near heap blocks, and calls to farmalloc() result in far heap blocks. In the compact, large, and huge models, all blocks come from the far heap, with calls to malloc() being re-routed through formalloc(). TurboC uses the variables first, last, and rover to maintain the near heap, and first, last, and rover to maintain the far heap.

While all of this is specific to TurboC, I am confident that Microsoft employs a similar scheme.

In closing, I'd like to say that although the segmented Intel architecture makes pointers and dynamic memory management tricky, there are a few caveats worth remembering. Most important among these is understanding what the compiler is doing. This includes knowing the effects of the memory model in use, the limitations of operand sizes and sizes of intermediate results, and the results of the standard type conversions. Nearly every time someone says that there is a bug in the compiler or the libraries, it can be tracked down to the programmer not being aware of what he or she is really asking the compiler to do.

Sincerely,

Michael S. Percy
420 Gallo Way
grimlok@hubcap.clemson.edu

Rather than guess, how about we let Microsoft explain it. See the next letter please. — rlw

Dear Mr. Ward:

First off, let me congratulate you on a fine magazine, one that I read with great interest each month.

I am writing in response to the letters you published from Jim Schimandle (February 1990) and David Grey Stahl (August 1990), regarding the behavior of malloc in a large model Microsoft C5. 1 program (also applicable to Microsoft C6.0).

The Microsoft C heap manager uses a sub-allocation scheme to minimize the number of calls made to DOS for memory, because getting memory from DOS is relatively slow. When malloc is first called, the heap manager asks DOS for an initial amount of heap space that is typically (for small blocks) much larger than the amount requested. Subsequent malloc calls are allocated out of this extra space, until it is exhausted. Then DOS must be called again to grow the segment. When the heap manager grows a segment, it rounds up the amount required to the next larger multiple of the global variable _amblksiz whose default value is 8K. When the segment can no longer be grown, a fresh segment is requested from DOS, and the process continues. This is described on page 33 of the Microsoft C5.1 Runtime Library Reference (and in the Microsoft C6.0 online help).

Mr. Schimandle's program allocates a series of 48,000 byte blocks. On the first call to malloc, a segment of 48K bytes is requested from DOS. On the second call to malloc, the heap manager sees that it cannot grow the segment to accommodate the second request because 48K + 48K is greater than 64K, the maximum size of a segment. Hence, it must request a new segment of 48K bytes from DOS. This continues until memory is exhausted. The program then calls free to return these blocks to the heap manager.

The second half of Mr. Schimandle's program now tries to allocate a series of 60,000 byte blocks. The heap manager finds that none of the segments it owns are large enough to satisfy the request and none of them can be grown (except possibly the last one). Accordingly, it asks DOS for a new 60K segment. But DOS does not have a segment this large left to give, and so the request fails.

If a program's memory requests are all large, then it may very well be reasonable to go to DOS directly for every allocation and free. The Microsoft C runtime library provides two ways to do this:

1. Replace the calls to malloc and free with calls to _dos_allocmem and _dos_freemem.

2. Include malloc.h and replace the calls to malloc and free with calls to halloc and hfree. These calls have somewhat more overhead because they are designed for allocations of greater than 64K.

In Microsoft C6.0, the program could call _heapmin before the second series of calls to malloc. The call to heapmin would cause the heap manager to scan all of its segments and return to DOS those that do not contain allocated blocks.

As Mr. Stahl points out in his letter, the mechanism used by malloc is a compromise between speed and fragmentation. I hope this will help shed some light on the subject.

Sincerely,

Richard Gillmann
Utilities Group Development Manager
Microsoft Corporation
One Microsoft Way
Redmond, WA 98052

I greatly appreciate your response. It's nice to know the compiler vendors are watching and that they're willing to share important information about their products with the programmers who depend upon them. — rlw

Dear Sir:

In testing Rex Jaeschke's assertion that there is no such thing as a negative constant in C ("Operators And The Precedence Table," C Users Journal, August, 1990) I find that the code generated by one compiler yields the size of an int when asked for sizeof(--32768) and that the code coughed out by a competing compiler returns the size of a long. With either compiler, constants more negative than --32768 are tagged as longs and those less negative but still less positive than +32768 are sized as ints.

This seems to mean that the compiler that is capable of storing --32768 in an int-sized object is indeed using a signed format to store the constant. Rex's comment therefore leads me to ask whether this behavior is just an unusual practice in C or whether it constitutes a violation of the ANSI Standard.

Although this side issue proved to be interesting, the exposition of the precedence table in the article was quite valuable to me and I look forward to future columns by Doctor C.

Sincerely,

Maynard A. Wright
6930 Enright Drive
Citrus Heights, CA 95621

--32768 must be long by ANSI rules.— pjp

Dear Mr. Ward:

I would like to offer some comments on the code presented in Mr. Felice's CCITT Cyclical Redundancy Check article in your September issue. First, taking the complement of the CRC prior to swapping the bytes does nothing for the algorithm. Second, taking the complement destroys a very elegant and useful property of the algorithm. The property I am referring to allows that if the CRC of a buffer is appended to the buffer, the CRC of this new buffer will be 0. This property is often used in communications hardware and software to easily check the integrity of data at intermediate points. Another handy change to the code presented would be to allow the CRC of a large chunk of data to be taken incrementally. This is easy enough to accomplish by adding a third parameter to the CRC call. This parameter is the starting constant for the first call. On subsequent calls one would pass in the CRC returned from the previous call. This is extremely handy on systems with limited memory or buffer space. I have enclosed a listing of my version of the algorithm, with examples showing the zero CRC property.

I enjoy your magazine greatly and look forward to Dr. Plauger's term as editor. Keep up the good work.

Sincerely

David W. Boyd
Sterline Software
1404 Fort Crook Rd
Bellevue, NE 68005

Dear Dr. Plauger:

Congratulations on your appointment as editor! It's a pleasure to read your "Standard C" column — technical writing at its best.

Last June I sent Kenneth Pugh the coding question that follows. No answer. I figure if anyone knows a solution you do. If you or an associate could help me out I would truly appreciate it:

Using C library functions, how can I show on the screen the ASCII character for each of these seven control codes or hexadecimal values?

BEL 07     CR 0d
BS 08      SUB la
HT 09      ESC lb
LF 0a
I want to display the seven characters the way printed charts picture them. But with printf(), for example, I beep, backspace, tab, etc. Help!

Good luck on the new job!

Sincerely,

Dale Wharton
2290 St-Antoine Street
Montreal QC H3J 1A7

Thanks for your kind words. Here are two ways to make nonprinting characters printable. The first is more robust, since it replaces any nonprinting character with a printable alternative. You must be content with a (suitably delimited) hexadecimal alternative:

void printx(int c) {

   printf(isprint(c) ? "%c" : "[%.2x]", c); }
If you want to print the names of certain control characters, as your letter indicates, you have to enumerate them:

void printxxx(int c) {
   static char esc[] =
       "\a\b\t\n\ r\x1a\x1b";
   static char prt[] =
"BEL\0BS\0\0HT\0\0LF\0\0CR\0\0SUB\0ESC";

   char *s = strchr(esc, c);

   if (s)
      printf(" [%s] ", prt [4*(s-prt)]);
   else
      printf("%c", c);
   }
Both of these approaches use more than one column to represent the funny characters. Unless your display has special graphics that you can map the characters to, you have to live with such a limitation. — pjp

Dear Ms. Ward:

Enclosed please find my check for $28 to renew my membership in the CUG and reinstate my subscription to The C Users Journal. I let my subscription lapse because the content of your magazine was several levels above my ability in C. My original membership was opened when I first purchased Borland's professional language package. At the time my main interest was in Pascal and I had not had any formal training in C. Since then I have had some formal training in C through the University of New Haven graduate program in Computer Science and the content of your magazine as well as the other membership benefits of CUG are more relevant.

Very truly yours

Alan Donn
Prentice Williams Rd.
Rural Route 2 Box 43A
Stonington, CT 06378

We're glad to have you back. — rlw

Dear Mr. Ward,

I am a relatively new C Programmer and enjoy your magazine very much. I have learned something new in every issue.

One of the things that I learned in the August 1990 issue is that a person cannot believe everything he reads. I am referring to the Book Review on page 125-6 by Harold C. Ogg. He "reviewed" the book C Programmer's Toolkit by Jack Purdum.

I bought that book two months ago after looking through it in the book store. My initial feelings were the same as Mr. Ogg's until I tried to compile the menu functions. The functions are so poorly written that they will not compile! In my many attempts to compile the code provided on the disk I found several small errors. For example there were several lines that did not end with a semicolon. It was easy to fix, but it took time and was annoying.

I also discovered some serious errors. One example is the function read_key(). In the header information for this function it says that the argument list is void. In the header file menu.h the function is declared with two arguments. In the function definition it has one argument. When read_key() is called by the function box_select() it is called with two arguments. When it is called by the function menu choice() it has one argument.

This is not the only example I could list. This book is hacker's code of the worst kind. I bought the book to save myself time not to debug code. I get enough practice on my own code.

I think that Mr. Ogg should have bought the book and tried to use some of the code instead of reading it in the book store. I am also less willing to believe any book review I read because of the shoddy work shown in this review. Your readers deserve better!

Steven Pierce
5249 Woodash Circle
West Valley City, UT 84120

May I suggest you forward the errors you've identified to Jack? I know he takes his books very seriously and will be concerned to correct them. (We can forward them for you if you don't have his address.) — rlw

Dear Mr. Ward,

Thanks for helping me communicate with Jim Hendrix. He shipped his out-of-print book by priority mail! I've found it helpful, nicely organized, and am glad to have it; thanks again to you.

In the September issue, "We Have Mail" there is a letter from Bill Sacramone. He has put many of my thoughts into words.

Now I wonder what I might have missed:

1. In the 1st quarter of 1990 — Would it be possible to send me photocopies of the index pages of those three issues? Then I could send $7.50 each for the intriguing issues (presuming availability).

2. How about those '88 and '89 listings? Would they be useful or make much sense without the text that accompanied them? Could be interesting to try to figure out, but there are plenty of those challenges in my own programs!

I think I'll try just the '89 listings for $20 If that works then I'll consider the '88 listings.

3. What about the earlier years of CUJ? Any plan to publish "The Best of CUJ Vol.I-V?"

As far as being of use to the group, I am willing but not able. I would be interested in knowing if there are a few other QL users among your 30,000-plus subscribers, if so perhaps we could form a QL-SIG within CUG.

About formats; My QL works with its own QDOS operating system using the 68008 chip. It handles disks of 720K using 512 bytes per sector, 9 sectors per track, 80 tracks per side, and two sides of either 3.5" or 5.25" disks.

I have an emulator/simulator for the QL that allows me to run IBM/PC-DOS programs from either 360K or 720K disks. My preference is for the 3.5" with 720K. Thus at home I can use small-C on the QL, and Mix-C or Turbo-C on the QL/IBM/emulator. At the University of Delaware I have access to the computing facilities. The system there is UNIX on a Vax 8650 until the end of 1990 when it will be supplanted by UNIX on Sun 4/490s. Actually the conversion has begun so I hope to convert soon and move my files over to the newer system. As I understand it my internet address will change from: hlschaaf@vaxl.udel.edu to hlschaaf-@brahms.udel.edu

I do hope the publisher's style will prevail when the new editor takes over. Hopefully the publisher will still find time to keep in touch with the readers ?

Thanks again,

H.L. Schaaf
3402 South Rockfield Drive
Wilmington, DE 19810-3229

I'm glad we were able to help. Better than an index to the back issues, we have a "back issue availabilty" guide that lists the major articles in each of the issues still in print.

A "Best of CUJ" volume has been on our project list forever. Maybe now that I don't have to edit, I can make some progress on that.

Don't worry about the publisher's style "prevailing" — that's what it means to be publisher. Seriously, I expect you'll be pleased once "pjp" is fully in harness. I think you'll find he is equally committed to maintaining a dialog — and quite possibly better equipped to say something useful. — rlw

Dear Mr. Ward,

I'm sure you're not used to getting letters from individuals like me. You see, Mr. Ward, I haven't got the foggiest what the CUJ writes about DOS, or RECS, or how many BYTES there are in a Big Mac. As far as computers in general however, I do know that the longer a hacker works at one, the more pain in the neck he gets. (I hear this from my chiropractor.)

I subscribe to CUJ since Leor joined your staff. He sent me one number at that time and when I told him that I kind of like it, he said: "We need new subscribers!" Well, like any parent I'm watching Leor's productivity. I noticed for example that one CUJ reader (D.J. Omond, of Athelstone, Australia) decided to continue subscribing to CUJ thanks to Leor's article. ("We have mail," July 1990).

Incidentally, I just found a few issues of "BDS C Users' Group," which Leor used to send me. That goes back to 1981, starting with Volume 1 — Issue 1. It gives me great pleasure to see the progress of your hard work.

Best wishes.

Sincerely,

Peter Zolman

P.S. I recently renewed my subscription. (Not necessarily because of Leor's articles). I wonder whether taking into account my age, I shouldn't be entitled to some kind of a discount. After all, I do get discounts all over (e.g. Home Improvement Center, a pharmacy, Santa Barbara Music Assoc. Seasonal Concerts, Time magazine and even at the Burger King.).

Peter M. Zolman
58 Via Alicia St.
Santa Barbara, CA 93108

You're absolutely right — I'm not used to getting letters from individuals like you. But it's fun all the same.

We're glad Leor has joined our little group. You have every reason to be proud of his work.

Sorry, but we don't offer "senior citizens discounts." How about our standard "employee's father" discount instead? I've told circulation to sign you up for a complimentary subscription. — rlw

Dear Mr. Ward:

In the letters section of volume 8, number 8 (Aug. 1990) you requested recommendations for good technical bookstores. Here is my favorite: Book Scientific, 18 E16th St., New York, NY 10003, (212) 206-1310. They have a pretty good selection in a rather small store, and they are willing to order from the publisher. They accept phone orders, and shipping and handling costs are minimal (personal checks accepted, though they don't take plastic).

Another bookstore (general, but has a large technical section) which I like very much is Borders Bookstore in Ann Arbor, Michigan. Unfortunately I don't have their address handy at the moment.

As others will probably tell you as well, there are the more commonly known computer book sellers: Cucumber Books, Jim Joyce's Bookstore, etc.

Several book clubs (e.g. McGraw-Hill's Electronics and Controller Engineers' Book Club, Library of Computer and Information Sciences, etc.) also have a fairly good selection at discount prices (though they'll get you with the shipping and handling costs).

Sincerely,

Fuat C. Baran
Columbia University in the City of New York
University Center For Computing Activities
UNIX Systems Group
612 West 115 Street
New York, NY 10025
fuat@columbia.edu

Thanks much. I had never heard of Book Scientific. I'll have to drop by if I ever get to New York again. — rlw

Dear CUJ:

Charles Havener's "Pricing A Meal: An Object-Oriented Example In C++" (August 1990) ignores the issue of developing C++ programs when expansion by end users is a requirement.

I assume:

In other words, the manager has the ability to point and click to change the price of an item — not the ability to declare C++ classes and recompile.

Havener's implementation fails to provide for:

1. A meal consisting of anything other than exactly one appetizer, one entree, and one dessert.

2. Additional classifications, such as Drink, at the level of Appetizer/Entree/Dessert.

3. Additional classifications one level lower (e.g. Soup as another Appetizer).

4. Changes in prices, discounts, or descriptions. As presented, the program needs to be recompiled if any of these change.

Here is a solution which addresses points 1, 3, and 4 (point 2 is dropped for lack of space and similarity with point 3). A full implementation would need to provide more error handling, connection of member functions to a user interface, etc.

Using simple objects to illustrate C++ concepts is fine. But a realistic problem such as Havener proposed deserves a more realistic solution. Your magazine is outstanding and you will be receiving a subscription order from me very soon!

Wondering How I Missed Volumes 1-7,

Vince Mehringer
3D/EYE, Inc.
2359 N. Triphammer Rd.
Ithaca, NY 14850
Voice: 607-257-1381
Internet: vince@eye.com

Yes, just how did you miss Volumes I — VII? Believe me; our circulation promotion people would like to know. — rlw

Listing 1