Re: memory allocation with malloc
At 01:16 AM 8/5/2008, Shyamal Shukla wrote:
Hi All,
I am trying to validate my understanding of how malloc works by means
of the below C program which tries to corrupt essential information
maintained by malloc for free() operation.
The program allocates 4, 12 byte blocks (internally 16 bytes are allocated
for each 12 byte block). Hence the total allocated space was 48 bytes.
As malloc maintains the (length of allocated block + 1), 4 bytes before the
returned pointer (from malloc), I have manipulated this length for the first
block and set it to 49 with the goal that a single free shall release all
these 4 blocks and a subsequent malloc of 15 bytes shall be from the address
of first block.
However, this does not happen. Can someone please correct my understanding
and provide me with a reference to the working of malloc() and free()?
#includestdio.h
int main(void)
{
char * ptr,* ptr1, *ptr2, * ptr3, * ptr4;
int * i;
int n,q,p;
int loop = 0;
ptr1 = (char *)malloc(12);
i = (int *)(ptr1 - 4);
printf(\n ptr1 = %p,%d \n,ptr1,*i);
printf(\n %d:%d:%d:%d\n,ptr1[-4],ptr1[-3],ptr1[-2],ptr1[-1]);
printf(\n %d:%d:%d:%d\n,ptr1[0],ptr1[1],ptr1[2],ptr1[3]);
printf(\n %d:%d:%d:%d\n,ptr1[4],ptr1[5],ptr1[6],ptr1[7]);
printf(\n %d:%d:%d:%d\n,ptr1[8],ptr1[9],ptr1[10],ptr1[11]);
*i = 49;
ptr2 = (char *)malloc(12);
i = (int *)(ptr2 - 4);
printf(\n ptr2 = %p,%d \n,ptr2,*i);
printf(\n %d:%d:%d:%d\n,ptr2[-4],ptr2[-3],ptr2[-2],ptr2[-1]);
ptr3 = (char *)malloc(12);
i = (int *)(ptr3 - 4);
printf(\n ptr3 = %p,%d \n,ptr3,*i);
printf(\n %d:%d:%d:%d\n,ptr3[-4],ptr3[-3],ptr3[-2],ptr3[-1]);
ptr4 = (char *)malloc(12);
i = (int *)(ptr4 - 4);
printf(\n ptr4 = %p,%d \n,ptr4,*i);
printf(\n %d:%d:%d:%d\n,ptr4[-4],ptr4[-3],ptr4[-2],ptr4[-1]);
free(ptr1);
printf(\n ANALYZE-\n);
printf(\n %d:%d:%d:%d\n,ptr1[-4],ptr1[-3],ptr1[-2],ptr1[-1]);
printf(\n %d:%d:%d:%d\n,ptr1[0],ptr1[1],ptr1[2],ptr1[3]);
printf(\n %d:%d:%d:%d\n,ptr1[4],ptr1[5],ptr1[6],ptr1[7]);
printf(\n %d:%d:%d:%d\n,ptr1[8],ptr1[9],ptr1[10],ptr1[11]);
ptr = (char *)malloc(15);
i = (int *)(ptr - 4);
printf(\n ptr = %p,%d \n,ptr,*i);
return;
}
Thanks and Regards,
Shyamal
I'm not quite sure what it is you want to accomplish with this
program. However, malloc and free work on the program's given data
area. This data area can be increased should there be a need for more
memory.
You should NEVER assume that memory blocks are contiguous. There are many
reasons why they would not be contiguous among them compiler
optimizations. If you really want to delve into how a program is executed,
have the compiler output the assembler code and look at that. The
assembler code will show exactly how and where the variables are
allocated. With such small amount of data used in your program, it is
possible the variables are all just on the stack.
You may want to check out the brk and sbrk man pages as they will give you
some information into how memory management was originally done as these
functions are lower-level than malloc and free.
-Derek
--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
___
freebsd-questions@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-questions
To unsubscribe, send any mail to [EMAIL PROTECTED]
memory allocation with malloc
Hi All,
I am trying to validate my understanding of how malloc works by means
of the below C program which tries to corrupt essential information
maintained by malloc for free() operation.
The program allocates 4, 12 byte blocks (internally 16 bytes are allocated
for each 12 byte block). Hence the total allocated space was 48 bytes.
As malloc maintains the (length of allocated block + 1), 4 bytes before the
returned pointer (from malloc), I have manipulated this length for the first
block and set it to 49 with the goal that a single free shall release all
these 4 blocks and a subsequent malloc of 15 bytes shall be from the address
of first block.
However, this does not happen. Can someone please correct my understanding
and provide me with a reference to the working of malloc() and free()?
#includestdio.h
int main(void)
{
char * ptr,* ptr1, *ptr2, * ptr3, * ptr4;
int * i;
int n,q,p;
int loop = 0;
ptr1 = (char *)malloc(12);
i = (int *)(ptr1 - 4);
printf(\n ptr1 = %p,%d \n,ptr1,*i);
printf(\n %d:%d:%d:%d\n,ptr1[-4],ptr1[-3],ptr1[-2],ptr1[-1]);
printf(\n %d:%d:%d:%d\n,ptr1[0],ptr1[1],ptr1[2],ptr1[3]);
printf(\n %d:%d:%d:%d\n,ptr1[4],ptr1[5],ptr1[6],ptr1[7]);
printf(\n %d:%d:%d:%d\n,ptr1[8],ptr1[9],ptr1[10],ptr1[11]);
*i = 49;
ptr2 = (char *)malloc(12);
i = (int *)(ptr2 - 4);
printf(\n ptr2 = %p,%d \n,ptr2,*i);
printf(\n %d:%d:%d:%d\n,ptr2[-4],ptr2[-3],ptr2[-2],ptr2[-1]);
ptr3 = (char *)malloc(12);
i = (int *)(ptr3 - 4);
printf(\n ptr3 = %p,%d \n,ptr3,*i);
printf(\n %d:%d:%d:%d\n,ptr3[-4],ptr3[-3],ptr3[-2],ptr3[-1]);
ptr4 = (char *)malloc(12);
i = (int *)(ptr4 - 4);
printf(\n ptr4 = %p,%d \n,ptr4,*i);
printf(\n %d:%d:%d:%d\n,ptr4[-4],ptr4[-3],ptr4[-2],ptr4[-1]);
free(ptr1);
printf(\n ANALYZE-\n);
printf(\n %d:%d:%d:%d\n,ptr1[-4],ptr1[-3],ptr1[-2],ptr1[-1]);
printf(\n %d:%d:%d:%d\n,ptr1[0],ptr1[1],ptr1[2],ptr1[3]);
printf(\n %d:%d:%d:%d\n,ptr1[4],ptr1[5],ptr1[6],ptr1[7]);
printf(\n %d:%d:%d:%d\n,ptr1[8],ptr1[9],ptr1[10],ptr1[11]);
ptr = (char *)malloc(15);
i = (int *)(ptr - 4);
printf(\n ptr = %p,%d \n,ptr,*i);
return;
}
Thanks and Regards,
Shyamal
--
Linux - because life is too short for reboots...
___
freebsd-questions@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-questions
To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation with malloc
On Tue, 5 Aug 2008 11:46:06 +0530, Shyamal Shukla [EMAIL PROTECTED] wrote: Hi All, I am trying to validate my understanding of how malloc works by means of the below C program which tries to corrupt essential information maintained by malloc for free() operation. The program allocates 4, 12 byte blocks (internally 16 bytes are allocated for each 12 byte block). Hence the total allocated space was 48 bytes. As malloc maintains the (length of allocated block + 1), 4 bytes before the returned pointer (from malloc), I have manipulated this length for the first block and set it to 49 with the goal that a single free shall release all these 4 blocks and a subsequent malloc of 15 bytes shall be from the address of first block. However, this does not happen. Can someone please correct my understanding and provide me with a reference to the working of malloc() and free()? That's because the original assumption is false. You wrote that malloc maintains the (length of allocated block + 1), 4 bytes before the returned pointer (from malloc). But that is not really true for all malloc() implementations, and it certainly isn't true for the `jemalloc' implementation that FreeBSD 7.X and 8.0-CURRENT use. ___ freebsd-questions@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation with malloc
On Tue, 05 Aug 2008 09:58:40 +0300, Giorgos Keramidas [EMAIL PROTECTED] wrote: On Tue, 5 Aug 2008 11:46:06 +0530, Shyamal Shukla [EMAIL PROTECTED] wrote: However, this does not happen. Can someone please correct my understanding and provide me with a reference to the working of malloc() and free()? That's because the original assumption is false. [...] I forgot to attach the link to the jemalloc paper, apologies. Here it is: http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf This describes how jemalloc works. This isn't a detailed line by line walk-through of the source, but it should provide a good starting point. Then you can always read the source of BSD malloc() at: http://svn.freebsd.org/viewvc/base/head/lib/libc/stdlib/malloc.c?view=log HTH, Giorgos ___ freebsd-questions@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation/deallocation (malloc experts needed)
On Thu, May 20, 2004 at 05:36:31PM +0900, Charlie Root wrote:
On Thu, May 20, 2004 at 01:42:00AM -0500, Dan Nelson wrote:
In the last episode (May 20), Till Plewe said:
My problem is essentially that freeing large numbers of small chunks
of memory can be very slow. I have run into this problem twice so
far.
Do you have a testcase? The attached program mallocs 1 million
128-byte blocks, then frees them. With MALLOC_OPTIONS set to jz (i.e.
no filling of freed memory), it takes .184 seconds to free them all.
With it set to J, it takes 1 second.
CPU: Intel Pentium III (909.96-MHz 686-class CPU)
...
I changed your program a little bit to allow freeing the memory in
random order which is closer to what happens when hash tables are
deleted. The test program now allocates NUM pointers to SIZE byte
memory chunks and then frees them. RANDOM 0 means the order in which
the items are freed is the same as the order of allocation, while
RANDOM 1 means that the memory is freed in (somewhat) random order
The data below shows that freeing the memory is the bottleneck.
(MALLOC_OPTIONS JZ, using jz gives essentially the same results perhaps
about 25% faster)
My current guess is that the part copied below of the function
free_bytes in /usr/src/lib/libc/stdlib/malloc.c is to blame
where linked lists are traversed to move/delete pages whose
status has changed. At least that would explain the quadratic
behaviour in the output of the test program below.
lines 1010-1028 of /usr/src/lib/libc/stdlib/malloc.c
if (info-free == 1) {
/* Page became non-full */
mp = page_dir + info-shift;
/* Insert in address order */
while (*mp (*mp)-next (*mp)-next-page info-page)
mp = (*mp)-next;
info-next = *mp;
*mp = info;
return;
}
if (info-free != info-total)
return;
/* Find remove this page in the queue */
while (*mp != info) {
mp = ((*mp)-next);
==
FreeBSD 5.2-CURRENT Sun May 2 08:40:29 JST 2004
CPU: Intel(R) Xeon(TM) CPU 2.40GHz (2392.05-MHz 686-class CPU)
test -n 20
NUM 120 RANDOM 0 SIZE 16 malloc: 0.140976 free: 0.113800
NUM 120 RANDOM 1 SIZE 16 malloc: 0.153176 free: 1.671878
test -n 21
NUM 121 RANDOM 0 SIZE 16 malloc: 0.277667 free: 0.228911
NUM 121 RANDOM 1 SIZE 16 malloc: 0.320030 free: 5.991513
test -n 22
NUM 122 RANDOM 0 SIZE 16 malloc: 0.492440 free: 0.466889
NUM 122 RANDOM 1 SIZE 16 malloc: 0.591442 free: 22.437910
test -n 23
NUM 123 RANDOM 0 SIZE 16 malloc: 1.106733 free: 0.929016
NUM 123 RANDOM 1 SIZE 16 malloc: 1.180094 free: 86.868541
test -n 24
NUM 124 RANDOM 0 SIZE 16 malloc: 2.040155 free: 1.866336
NUM 124 RANDOM 1 SIZE 16 malloc: 2.250588 free: 356.746455
test -n 25
NUM 125 RANDOM 0 SIZE 16 malloc: 4.280042 free: 3.716874
NUM 125 RANDOM 1 SIZE 16 malloc: 4.567206 free: 1497.213212
test -n 26
NUM 126 RANDOM 0 SIZE 16 malloc: 8.543537 free: 7.612657
NUM 126 RANDOM 1 SIZE 16 malloc: 9.055712 free: 6187.992730
==
FreeBSD 5.2-CURRENT Wed May 19 10:59:08 JST 2004
CPU: AMD Opteron(tm) Processor 248 (2205.01-MHz K8-class CPU)
test -n 20
NUM 120 RANDOM 0 SIZE 16 malloc:0.124275 free:0.067746
NUM 120 RANDOM 0 SIZE 16 malloc:0.098449 free:0.066730
NUM 120 RANDOM 1 SIZE 16 malloc:0.119348 free:1.435530
NUM 120 RANDOM 1 SIZE 16 malloc:0.099841 free:1.428259
test -n 21
NUM 121 RANDOM 0 SIZE 16 malloc:0.213471 free:0.134132
NUM 121 RANDOM 0 SIZE 16 malloc:0.199287 free:0.132293
NUM 121 RANDOM 1 SIZE 16 malloc:0.184251 free:4.998957
NUM 121 RANDOM 1 SIZE 16 malloc:0.186739 free:4.849894
test -n 22
NUM 122 RANDOM 0 SIZE 16 malloc:0.464616 free:0.255515
NUM 122 RANDOM 0 SIZE 16 malloc:0.425375 free:0.254138
NUM 122 RANDOM 1 SIZE 16 malloc:0.404901 free:17.264623
NUM 122 RANDOM 1 SIZE 16 malloc:0.394420 free:18.328755
test -n 23
NUM 123 RANDOM 0 SIZE 16 malloc:0.819199 free:0.514065
NUM 123 RANDOM 0 SIZE 16 malloc:0.858903 free:0.520739
NUM 123 RANDOM 1 SIZE 16 malloc:0.830438 free:67.556339
NUM 123 RANDOM 1 SIZE 16 malloc:0.821419 free:67.287440
test -n 24
NUM 124 RANDOM 0 SIZE 16 malloc:1.726636 free:1.032238
NUM 124 RANDOM 0 SIZE 16 malloc:1.709127 free:1.028701
NUM 124 RANDOM 1 SIZE 16 malloc:1.615758 free:290.153962
NUM 124 RANDOM 1 SIZE 16 malloc:1.645739 free:279.887830
test -n 25
NUM 125 RANDOM 0 SIZE 16 malloc:3.429280 free:2.044097
NUM 125 RANDOM 0 SIZE 16 malloc:3.486703 free:2.026912
NUM 125 RANDOM 1 SIZE 16 malloc:3.536784 free:1172.642691
NUM 125 RANDOM 1 SIZE 16 malloc:3.481226 free:1176.604815
==
test program
#include stdio.h
#include stdlib.h
#include sys/time.h
Re: memory allocation/deallocation (malloc experts needed)
On Thu, May 20, 2004 at 09:28:12AM -0400, Chuck Swiger wrote: Till Plewe wrote: My problem is essentially that freeing large numbers of small chunks of memory can be very slow. I have run into this problem twice so far. [ ... ] One solution would be to divide the memory in larger regions and to tell malloc which chunk to use for the next few calls, respectively when a whole chunk could be freed. But I don't know how to do this. Consider using (or searching for information about) a zone-based malloc. NEXTSTEP used one and hence Darwin/OS X probably have sources available for you to consider... Thanks. I will give it a try. Although I was hoping to find somebody who has already an alternative malloc implementation running. - Till ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation/deallocation (malloc experts needed)
In the last episode (May 20), Till Plewe said:
My problem is essentially that freeing large numbers of small chunks
of memory can be very slow. I have run into this problem twice so
far.
Do you have a testcase? The attached program mallocs 1 million
128-byte blocks, then frees them. With MALLOC_OPTIONS set to jz (i.e.
no filling of freed memory), it takes .184 seconds to free them all.
With it set to J, it takes 1 second.
CPU: Intel Pentium III (909.96-MHz 686-class CPU)
--
Dan Nelson
[EMAIL PROTECTED]
#include stdio.h
#include stdlib.h
#include sys/time.h
#include sys/resource.h
#define NUM 1048576
#define SIZE 128
void *mypointers[NUM];
struct timeval elap;
struct rusage r_s, r_e;
int main(void)
{
int i;
printf(malloc:);
fflush(stdout);
for (i = 0; i NUM; i++)
{
mypointers[i] = malloc(SIZE);
}
printf(done.\nfree:);
fflush(stdout);
getrusage(RUSAGE_SELF, r_s);
for (i = 0; i NUM; i++)
{
free(mypointers[i]);
}
getrusage(RUSAGE_SELF, r_e);
timersub(r_e.ru_utime, r_s.ru_utime, elap);
printf(done. %ld.%06ld\n, elap.tv_sec, elap.tv_usec);
return 0;
}
___
[EMAIL PROTECTED] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-questions
To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation/deallocation (malloc experts needed)
On Thu, May 20, 2004 at 01:42:00AM -0500, Dan Nelson wrote: In the last episode (May 20), Till Plewe said: My problem is essentially that freeing large numbers of small chunks of memory can be very slow. I have run into this problem twice so far. Do you have a testcase? The attached program mallocs 1 million 128-byte blocks, then frees them. With MALLOC_OPTIONS set to jz (i.e. no filling of freed memory), it takes .184 seconds to free them all. With it set to J, it takes 1 second. CPU: Intel Pentium III (909.96-MHz 686-class CPU) ... I get NUM SIZEMALLOC_OPTIONS time 1058576 128 jz 0.044 1058576 128 JZ 0.13 128*1048576 8 jz 5.28 128*1048576 8 JZ 7.70 200*1048576 8 jz 8.25 200*1048576 8 JZ 13.17 with CPU: AMD Opteron(tm) Processor 248 (2205.02-MHz K8-class CPU) but with NUM 255*1048576 I run out of memory (although I have 6GB and your test program should only use about (sizeof(void*)+SIZE)*NUM=(8+8)*255*1048576=4GB) Using NUM 256*1048576, SIZE 8 I get # gcc -o test test.c /var/tmp//ccLxywz6.s: Assembler messages: /var/tmp//ccLxywz6.s:95: Error: .COMMon length (-2147483648.) 0! Ignored. /var/tmp//ccLxywz6.s:95: Warning: rest of line ignored; first ignored character is `,' In any case since I have the pointers in a hash table (Judy array) rather than an array I need extra time for look-up/deleting the entry in the hash table as well. If I could get malloc to use a fixed memory region for the part I want to delete (both for the hash table and the information pointed to) deletion should take no time at all. In my program I get times like this DATA 6.553015 sec JUDY 7.593997 sec deleted 1272062 hash entries, freed 28542840(Judy) + 15264744(data) bytes where judy translates hash values to pointers pointing to simple structs. Since I want to delete up to 10^8 entries the times get quite bad. I guess quite a bit of the extra time is spent jumping around in memory. Your test program frees memory in the order it was allocated which should be a quite regular pattern. I will test some more and then post some more details. Thanks for your answer. - Till ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: memory allocation/deallocation (malloc experts needed)
Till Plewe wrote: My problem is essentially that freeing large numbers of small chunks of memory can be very slow. I have run into this problem twice so far. [ ... ] One solution would be to divide the memory in larger regions and to tell malloc which chunk to use for the next few calls, respectively when a whole chunk could be freed. But I don't know how to do this. Consider using (or searching for information about) a zone-based malloc. NEXTSTEP used one and hence Darwin/OS X probably have sources available for you to consider... -- -Chuck ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
memory allocation/deallocation (malloc experts needed)
My problem is essentially that freeing large numbers of small chunks of memory can be very slow. I have run into this problem twice so far. 1) Shutting down python can take several minutes if I have used large dictionaries. The solution I use here is to exit python without freeing the allocated memory (not really a good solution). 2) Freeing large hashtables in C. (No solution yet.) For these hashtables I can fairly easily divide the data into groups which could be deleted together. If I have all this data in one predefined region of memory then deleting them would be very fast. However in order to keep memory consumption as low as possible without sacrificing speed I am using Judy arrays (see the Judy project at source forge). But that means I have no direct control over how malloc is called. One solution would be to divide the memory in larger regions and to tell malloc which chunk to use for the next few calls, respectively when a whole chunk could be freed. But I don't know how to do this. Cyclone's regions seem to provide more or less what I need but cyclone works on neither CURRENT nor on amd64. Any suggestions where to look/what to read are greatly appreciated - Till ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-questions To unsubscribe, send any mail to [EMAIL PROTECTED]
