problem with dyn. extending/shrinking array


C

cerr

Hi There,

I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.
I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
if(realloc(buffer,++buffersz)!=NULL){
if(buffersz){
fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv, ch, ch);
buffer[buffersz-1]=ch;
}else
fprintf(DEBUG,"ERROR: invalid buffer size(%Ld), cant receive data!
\r\n",buffersz);
} else{
fprintf(DEBUG,"Out of memory, allocated %Ld Bytes\r\n",buffersz);
if (buffersz%1024==0){
fprintf(DEBUG, "%LdKB allocated\r\n",buffersz/1024);
}
}
and then in my main, i have a loop to send the data out and i do it
like this:
while(RC1IE || buffersz>1){
if(buffersz)
{
fputc(buffer[0],MCU1);
if(realloc(buffer,--buffersz)!=NULL){
fprintf(DEBUG, "ERROR:Failed to shrink buffer %Ld!\r\n",
buffersz);
}
}
}
But that doesn't quite seem to work correctly. I think I 'm messing my
array up with my realloc() calls. Any suggestions are appreciated!
Thank you!

BTW: I'm using the CCS compiler version 4.119
 
Ad

Advertisements

C

cerr

 cerr said:
Hi There,
I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.
I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
     if(realloc(buffer,++buffersz)!=NULL){
       if(buffersz){
             fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv,ch, ch);
             buffer[buffersz-1]=ch;

Unless your implementation guarentees it reallocs in place (ANS C does not make
this guarentee), your code is wrong. The address of the re-allocated block,
returned by realloc, can be different from the input address. Your code should
be more like
    char *buffer1 = realloc(buffer,++buffersz);
    if (!buffer1 && buffersz) {
        fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv, ch, ch);
    }
    buffer = buffer1; buffer[buffersz-1]=ch;
                       if(realloc(buffer,--buffersz)!=NULL){
in my doc realloc() says to the return value:
A pointer to the possibly moved allocated memory, if any. Returns
null otherwise.
Now we pass buffer as a pointer to resize and store the return value
in buffer1, is the content from buffer now automatically in buffer1?
it says POSSIBLY moved allocated memory... What does this mean
exactly? :eek:
Cause I have now:
int8 *buffer1 = realloc(buffer,++buffersz);
if (!buffer1 && buffersz) {
fprintf(DEBUG,"ERROR: Couldn't allocate memory at 0x
%x",buffer1);
}
buffer = buffer1;
buffer[buffersz-1]=ch;
but ch on the bottom doesn't seem to be going anywhere...

Same here. The buffer can move when shrunk.

As a side note if the buffer can move on realloc, the above code can exhibit
quadratic behaviour. This why many people double the buffer on realloc and do
not shrink it.
    size_t actualsize = 0, logicalsize = 0; char *buffer = 0;
    if (logicalsize++>=actualsize) {
        actualsize = 2*logicalsize; char *buffer1 = realloc(buffer, actualsize);
        if (!buffer1) ...
        buffer = buffer1;
    }
    buffer[logicalsize-1] = ch;
    ...
    --logicalsize;
However this is an optimisation and not mandatory.

--
Damn the living - It's a lovely life.           I'm whoever youwant me to be.
Silver silverware - Where is the love?       At least I can stay incharacter.
Oval swimming pool - Where is the love?    Annoying Usenet one post at a time.
Damn the living - It's a lovely life.                      I'm lost in a fog.
 
E

Eric Sosman

Hi There,

I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.
I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
if(realloc(buffer,++buffersz)!=NULL){

This is NFG for multiple reasons.

First, the purely C reason: That's not how realloc() works. Since
it may need to move the entire buffer to a new memory area (if it can't
grow the old area "in place"), after the call `buffer' may no longer be
pointing to anything useful. It might be pointing to the (enlarged)
buffer, or perhaps the buffer got moved elsewhere and `buffer' now
points at memory that has been freed. realloc() returns a pointer to
the possibly moved memory area; you need to set `buffer' to that value.

... except that `buffer = realloc(buffer, ++buffersz)' would also
be a bad idea, because realloc() can fail: What if a temporary glitch
has forced the buffer to get really really big, and realloc() can't
find a large enough memory area to hold it? In this case realloc()
returns NULL to say "Sorry; I can't help you," and if you assign that
NULL to `buffer' you have just lost your only record of where the
memory area used to be. You can't even free() it any more, much less
make productive use of it.

Okay, now to the non-C or non-strictly-C reasons. First, you
mention that this is happening in "an interrupt function," which
usually means it happens at some entirely unpredictable moment. Well,
what if the program was in the middle of a realloc() when the interrupt
occurred? Or in the middle of a malloc() or realloc() or free(), all
of which probably use and modify the same data structures realloc()
needs to use? Or even if it's in none of them, what if it has just
fetched the value of `buffer' into a register, and then the interrupt
occurs and realloc() moves the buffer to somewhere else, and then the
main-line resumes, now using a stale value? It's like hearing the
"ding" and walking through the elevator doors without looking: sometimes
you get a lift, sometimes you get the shaft.

And another non-strictly-C concern: realloc() is not instantaneous.
It probably takes a non-negligible amount of time to figure out whether
it can grow the memory area in place and to update its metadata to
reflect the new size, and it probably takes even more time when it's
forced to copy the old data from one place to a new, larger place.
And you want to incur all this work on every single character? That's
like making six round trips to the beer store instead of making one
and buying a six-pack.
if(buffersz){
fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv, ch, ch);

We're still in "an interrupt function," right? Well, fprintf() is
also not guaranteed to be re-entrant; if the interrupted code happened
to be in the middle of an fprintf() or allied call, there's no telling
what might happen here. (And what if fprintf() calls realloc()?)
buffer[buffersz-1]=ch;
}else
fprintf(DEBUG,"ERROR: invalid buffer size(%Ld), cant receive data!
\r\n",buffersz);
} else{
fprintf(DEBUG,"Out of memory, allocated %Ld Bytes\r\n",buffersz);
if (buffersz%1024==0){
fprintf(DEBUG, "%LdKB allocated\r\n",buffersz/1024);
}
}
and then in my main, i have a loop to send the data out and i do it
like this:
while(RC1IE || buffersz>1){

Since the "interrupt function" might be changing `buffersz' even
as you're trying to test it, you can't rely on the test; it's
meaningless.
if(buffersz)
{
fputc(buffer[0],MCU1);
if(realloc(buffer,--buffersz)!=NULL){

Still mis-using realloc(), and still vulnerable to reentrancy and
simultaneous-update problems. Also, even if this worked you'd be
sending the same character over and over again:

Receive A, buffer holds A
Receive B, buffer holds AB
Transmit buffer[0] == A
Shrink buffer, it now holds A (you threw away the B)
Receive C, buffer holds AC
Transmit buffer[0] == A
Shrink buffer, it now holds A (you threw away the C)
Receive D, buffer holds AD
...
fprintf(DEBUG, "ERROR:Failed to shrink buffer %Ld!\r\n",
buffersz);
}
}
}
But that doesn't quite seem to work correctly. I think I 'm messing my
array up with my realloc() calls. Any suggestions are appreciated!

One suggestion is that you learn C before trying to proceed
with this or any other project. There's no shame in not knowing a
particular language (I'm utterly ignorant of Estonian), but trying
to use a language you don't know can only get you into trouble (I
asked an Estonian girl what time it was and she slapped my face).

Beyond that I'm not sure what to recommend. Programming for
parallel activities is poorly supported in most languages, and is
particularly poorly supported in C. That's not to say it can't be
done, nor that it can't be done well; it can and is. But getting it
to work requires that you rely on frameworks and conventions and
patterns that lie outside the language, and are usually particular
to the environment you're using. It's not enough to learn C; you
must also learn the C-with-extras environment you're writing for.
Perhaps a careful study of existing (working!) programs for that
environment would help -- but the study can't be "careful" until
you know C well enough to understand what you're reading.

Good luck, but don't expect overnight success.
 
F

Francois Grieu

I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.

If you can guarantee that UART1 receives data at a rate appreciably
lower than that of UART2, and nothing else write to UART2, and
there is no hardware handshake on UART2 to slow it down, then you
may not need any buffering, and can stuff the byte read from UART 1
into UART2 right at interrupt level; you should nevertheless wait
until UART2 is ready (it will almost always be, and if not the wait
will be small).
When the bit rate of UART1 is lower than that of UART2 (by say 4%)
and all the UARTs use the same format, (including the one of the
device sending to UART1, at a bit rate close to that of UART1),
that will always work. If the UARTs are at the same bit rate, you
may program the UART of the device sending to UART1 with 1.5 or 2
stop bits (and 1 stop bit in UART1 and UART2) to obtain some design
headroom.
Else, buffering might be needed. Fixed size buffers are simple and
should be the first considered design option.

I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
if(realloc(buffer,++buffersz)!=NULL){

As pointed out by others,
~ there is no insurance that realloc does not move the buffer; that
could be fixed by buffer = realloc(buffer,++buffersz)
(and a total disregard for out-of-memory condition)
~ in general, you can not realloc in an interrupt, for a variety
of reasons including
~ that may be too slow
~ another malloc/realloc/free might be underway

If you want a variable-size buffer expanded at interrupt time, the
best technique I have practiced is a pool of fixed-size buffers,
kept in a linked list; this way you achieve fast and deterministic
expansion/shrink time for the buffer.

Francois Grieu
 
I

ImpalerCore

Hi There,

I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.
I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
          if(realloc(buffer,++buffersz)!=NULL){
            if(buffersz){
                  fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv, ch, ch);
                  buffer[buffersz-1]=ch;
                }else
                  fprintf(DEBUG,"ERROR: invalid buffer size(%Ld), cant receive data!
\r\n",buffersz);
            } else{
            fprintf(DEBUG,"Out of memory, allocated %Ld Bytes\r\n",buffersz);
            if (buffersz%1024==0){
                  fprintf(DEBUG, "%LdKB allocated\r\n",buffersz/1024);
            }
          }
and then in my main, i have a loop to send the data out and i do it
like this:
                        while(RC1IE || buffersz>1){
                          if(buffersz)
                          {
                            fputc(buffer[0],MCU1);
                            if(realloc(buffer,--buffersz)!=NULL){
                                  fprintf(DEBUG, "ERROR:Failed to shrink buffer %Ld!\r\n",
buffersz);
                                }
                          }
                        }
But that doesn't quite seem to work correctly. I think I 'm messing my
array up with my realloc() calls. Any suggestions are appreciated!
Thank you!

BTW: I'm using the CCS compiler version 4.119

Hi There,

I am working on a little microcontroller application and i want to
receive bytes from UART 1(rs232) and pass them on to UART2 with as
little buffering as possible.
I have an interrupt function that kicks in when I can receive a byte
and I do this:
// buffer was allocated with calloc(1,1)
if(realloc(buffer,++buffersz)!=NULL){
if(buffersz){
fprintf(DEBUG,"NoBrcv %Ld %c 0x%x\r\n",Brcv, ch, ch);
buffer[buffersz-1]=ch;
}else
fprintf(DEBUG,"ERROR: invalid buffer size(%Ld), cant receive data!
\r\n",buffersz);
} else{
fprintf(DEBUG,"Out of memory, allocated %Ld Bytes\r\n",buffersz);
if (buffersz%1024==0){
fprintf(DEBUG, "%LdKB allocated\r\n",buffersz/1024);
}
}
and then in my main, i have a loop to send the data out and i do it
like this:
while(RC1IE || buffersz>1){
if(buffersz)
{
fputc(buffer[0],MCU1);
if(realloc(buffer,--buffersz)!=NULL){
fprintf(DEBUG, "ERROR:Failed to shrink buffer %Ld!\r\n",
buffersz);
}
}
}
But that doesn't quite seem to work correctly. I think I 'm messing my
array up with my realloc() calls. Any suggestions are appreciated!
Thank you!

BTW: I'm using the CCS compiler version 4.119

Just a couple of points to consider in addition to these other posts.

Typically you want your interrupt functions to be in and out as fast
as possible, to avoid the interrupt in an interrupt debacle. I've
only used one MCU and its library support does not have dynamic
memory, but I imagine that doing a realloc of any kind is a bad idea
in an interrupt. Functions of the printf are very bad for similar
reasons. In an interrupt, I typically set a bitflag that the main
while loop detects that moves the character into some non-volatile
declared circular buffer to ensure that the interrupt is ready for the
next ping. I might need to move it to a separate holding character
depending on how slow main responds to other events. If your app has
to update an 128x64 pixel LCD display, read an array of 5 temperature/
humidity sensors at a rate of once a second, respond to serial
commands, handle a 3-button menu interface, and store data to EEPROM,
you obviously can't shove all this into the interrupt handler.

In your scenario, if the response to each of your events is fast,
little work needs to be done. If your MCU app is just mirroring
serial port traffic at the same rate, there's very little if any
buffering that I would think needs to be done. A single character
buffer may be all that is needed, or if the app is busy and lag from
processing other events is severe, a small fixed size buffer can cache
the collected characters until the main program can catch up. If it's
burst traffic, then you just have to cache enough space to store
characters to allow main to finish processing its current event before
sending the accumulated data. If your throughput is constant and
hovers near the max baud rate, then one needs to be quite a bit more
careful.

One thing that really helps me is using an oscilloscope and toggling a
pin to measure time periods within the program. It can help give you
an idea of how much time a particular task takes. You set the pin
high at the start of your event, and set it low at the end, and you
can measure the time while the pulse is high to estimate the time
needed to process your event. This is useful to ensure that the speed
of your event handling exceeds the rate of input.

If you have synchronous events, like taking a temperature sensor
measurement at a rate of once a second, you can use a timer interrupt
to update a global clock with millisecond precision and use timeouts
to signal when events happen. If you have a clock with millisecond
precision that you increment based on a hardware timer, you need to be
wary when reading or writing the clock variables.

Here's a code snippet that demonstrates how I interact with an
interrupt to maintain a millisecond clock. I cut out most of the
fluff, and hopefully you can see the main points.

\code snippet

/* Timer0 interrupt service routine that increments a counter. */
void interrupt isr( void );

/* The TMR0 counter bias. */
#define TMR0_BIAS 6

/* The PIC18F system clock. */
volatile long int tmr0_s;
volatile int tmr0_tick;

/* Get the PIC time in seconds. */
time_t gettime_s( time_t* t );
void gettime( c_time_value_t* tv );

....

void gettime( c_time_value_t* tv )
{
if ( tv )
{
TMR0IE = 0;
tv->sec = tmr0_s;
tv->usec = (long int)tmr0_tick * 1000;
TMR0IE = 1;
}
}

time_t gettime_s( time_t* t )
{
time_t tv;

TMR0IE = 0;
tv = tmr0_s;
TMR0IE = 1;

if ( t ) {
*t = tv;
}

return tv;
}

void interrupt isr( void )
{
if( (TMR0IE) && (TMR0IF) && (TMR0IP) )
{
/*
* The output pins RB6 and RB7 are toggled to measure to overhead
* of the ISR implementation. They demonstrate one method to
* measure code execution time using an oscilloscope.
*/
RB6 ^= 1;

TMR0 = TMR0_BIAS; /* 0.375 ns (3 inst) */
TMR0IF=0; /* 0.125 ns (1 inst) */
++tmr0_tick; /* 0.500 ns (4 inst) */

if ( tmr0_tick == C_TICKS_PER_SECOND ) /* 0.750 ns (6 inst) */
{
++tmr0_s; /* 0.750 ns (6 inst) */
tmr0_tick = 0; /* 0.500 ns (4 inst) */
}

RB7 ^= 1; /* 0.125 ns (1 inst) */
}
}
\endcode

Note the disabling of timer interrupt in gettime 'TMR0IE = 0;',
followed by updating the timestamp to the global clock, then re-
enabling the interrupt. Note that when I disable the interrupt in
gettime 'TMR0IE = 0', it's possible that during the time I update the
timestamp 'tv->sec = tmr0_s; tv->usec = (long int)tmr0_tick * 1000;',
the 1ms timer interrupt could have triggered. The interrupt won't
happen until I re-enable the interrupt at 'TMR0IE = 1', which can
introduce a little bit of jitter. As an aside, this was running on a
chip configured with a clock speed of 32MHz or 8MIPS (millions of
instructions per second), so the jitter effect is negligible in my
application. If the clock speed is slower, or the data rates approach
clock speed limitations, it can be problematic.

Also, in the ISR, I toggle pins RB6 and RB7 to generate square waves
so I can actually see whether my hardware timer is set correctly, and
whether my clock has any cumulative skew (to make sure that any jitter
effects are not cumulative).

Hope it helps.

Best regards,
John D.
 
J

James Waldby

.
TMR0 = TMR0_BIAS; /* 0.375 ns (3 inst) */
TMR0IF=0; /* 0.125 ns (1 inst) */
++tmr0_tick; /* 0.500 ns (4 inst) */ ....
As an aside, this was running on a chip configured with
a clock speed of 32MHz or 8MIPS [...]

If the comments are right, you're mistaken about that
clock speed. 0.125 ns for 4 cycles is 32GHz or 8GIPS.
Which PIC18F were you using, and what was the power consumption?
 
Ad

Advertisements

I

ImpalerCore

On Wed, 16 Mar 2011 08:46:26 -0700, ImpalerCore wrote:

...
   TMR0 = TMR0_BIAS; /* 0.375 ns (3 inst) */
   TMR0IF=0;         /* 0.125 ns (1 inst) */
   ++tmr0_tick;      /* 0.500 ns (4 inst) */ ...
As an aside, this was running on a chip configured with
a clock speed of 32MHz or 8MIPS [...]

If the comments are right, you're mistaken about that
clock speed.  0.125 ns for 4 cycles is 32GHz or 8GIPS.
Which PIC18F were you using, and what was the power consumption?

Good catch. I have the wrong units there. At 32MHz, each clock tick
is 1/32MHz or 31.25ns. Each instruction takes 4 clock cycles, or 125
ns. The hardware for the project uses a PIC18F4610, but it's starting
to get pretty tight with all the feature creep they keep adding.

Thanks for the documentation bug report :)

Best regards,
John D.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top