To expand on Lee's post, you've got 4k ram ('data') and 64k flash ('program') on the ATmega644.avr-size reports that my build uses 3352 bytes of 'data' and 10746 bytes of 'program' - this is confusing. Where should I look to determine how much space is left on the chip?
The ram will be used for global/static variables and for the call stack. You can explicitly request that items be allocated memory from the 'data' section (ram) in avr-asm with ".section .bss". You can place data in 'program' space (flash) with ".section .text".
If you're coding in C, any variables declared outside of a function (or inside of one, but preceded with the static keyword) will be placed in the 4k of ram starting from position 0x000 all the way to 0xfff (4096 bytes). Variables declared inside of a function will be reserved space on the stack when the function is called (unless registers are available), along with the return address and function parameters for which no registers are available. The stack (also residing in ram) starts at 0xfff and works downwards (although we think of it as building upwards). Thus, if you eat up all your ram with static and global variables (or have large function chains or recursive calls), you can get into a problem where your stack collides with your globals/statics. So it's a good idea to leave some room for the stack to grow.
'Program' space in C will be used by your code expressions/logic. You can also place data in program space with the PROGMEM macro; it looks like this:
You can load it into ram with the strcpy_P and memcpy_P functions (you'll need to include <avr/pgmspace.h>). This is useful because these chips have such little ram, so we make the tradeoff in cycles required to load this data when required. We also realize that changes cannot be made to this data at runtime (although when loaded into ram, that copy in ram may be altered).char blinkyName[] PROGMEM = "\"BLINKY\"";
So you can see that ram ('data') is dynamic and very scarce, while flash ('program') is static but relatively plentiful.
As for the malloc library include, maybe someone else will know for sure, but I'd guess that you're using a library which in turn makes use of malloc. I'm not entirely sure, otherwise.
My apologies if much of this was recapping information that you already know, but it might be a useful intro to others.