memory.c revision 263870ec0857c095882d6cfb164852ed7e4baeaf 
1/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3%                                                                             %
4%                                                                             %
5%                                                                             %
6%                    M   M  EEEEE  M   M   OOO   RRRR   Y   Y                 %
7%                    MM MM  E      MM MM  O   O  R   R   Y Y                  %
8%                    M M M  EEE    M M M  O   O  RRRR     Y                   %
9%                    M   M  E      M   M  O   O  R R      Y                   %
10%                    M   M  EEEEE  M   M   OOO   R  R     Y                   %
11%                                                                             %
12%                                                                             %
13%                     MagickCore Memory Allocation Methods                    %
14%                                                                             %
15%                              Software Design                                %
16%                                   Cristy                                    %
17%                                 July 1998                                   %
18%                                                                             %
19%                                                                             %
20%  Copyright 1999-2014 ImageMagick Studio LLC, a non-profit organization      %
21%  dedicated to making software imaging solutions freely available.           %
22%                                                                             %
23%  You may not use this file except in compliance with the License.  You may  %
24%  obtain a copy of the License at                                            %
25%                                                                             %
26%    http://www.imagemagick.org/script/license.php                            %
27%                                                                             %
28%  Unless required by applicable law or agreed to in writing, software        %
29%  distributed under the License is distributed on an "AS IS" BASIS,          %
30%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
31%  See the License for the specific language governing permissions and        %
32%  limitations under the License.                                             %
33%                                                                             %
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35%
36%  Segregate our memory requirements from any program that calls our API.  This
37%  should help reduce the risk of others changing our program state or causing
38%  memory corruption.
39%
40%  Our custom memory allocation manager implements a best-fit allocation policy
41%  using segregated free lists.  It uses a linear distribution of size classes
42%  for lower sizes and a power of two distribution of size classes at higher
43%  sizes.  It is based on the paper, "Fast Memory Allocation using Lazy Fits."
44%  written by Yoo C. Chung.
45%
46%  By default, ANSI memory methods are called (e.g. malloc).  Use the
47%  custom memory allocator by defining MAGICKCORE_ZERO_CONFIGURATION_SUPPORT
48%  to allocate memory with private anonymous mapping rather than from the
49%  heap.
50%
51*/
52
53/*
54  Include declarations.
55*/
56#include "MagickCore/studio.h"
57#include "MagickCore/blob.h"
58#include "MagickCore/blob-private.h"
59#include "MagickCore/exception.h"
60#include "MagickCore/exception-private.h"
61#include "MagickCore/memory_.h"
62#include "MagickCore/memory-private.h"
63#include "MagickCore/resource_.h"
64#include "MagickCore/semaphore.h"
65#include "MagickCore/string_.h"
66#include "MagickCore/utility-private.h"
67
68/*
69  Define declarations.
70*/
71#define BlockFooter(block,size) \
72  ((size_t *) ((char *) (block)+(size)-2*sizeof(size_t)))
73#define BlockHeader(block)  ((size_t *) (block)-1)
74#define BlockSize  4096
75#define BlockThreshold  1024
76#define MaxBlockExponent  16
77#define MaxBlocks ((BlockThreshold/(4*sizeof(size_t)))+MaxBlockExponent+1)
78#define MaxSegments  1024
79#define MemoryGuard  ((0xdeadbeef << 31)+0xdeafdeed)
80#define NextBlock(block)  ((char *) (block)+SizeOfBlock(block))
81#define NextBlockInList(block)  (*(void **) (block))
82#define PreviousBlock(block)  ((char *) (block)-(*((size_t *) (block)-2)))
83#define PreviousBlockBit  0x01
84#define PreviousBlockInList(block)  (*((void **) (block)+1))
85#define SegmentSize  (2*1024*1024)
86#define SizeMask  (~0x01)
87#define SizeOfBlock(block)  (*BlockHeader(block) & SizeMask)
88
89/*
90  Typedef declarations.
91*/
92typedef enum
93{
94  UndefinedVirtualMemory,
95  AlignedVirtualMemory,
96  MapVirtualMemory,
97  UnalignedVirtualMemory
98} VirtualMemoryType;
99
100typedef struct _DataSegmentInfo
101{
102  void
103    *allocation,
104    *bound;
105
106  MagickBooleanType
107    mapped;
108
109  size_t
110    length;
111
112  struct _DataSegmentInfo
113    *previous,
114    *next;
115} DataSegmentInfo;
116
117typedef struct _MagickMemoryMethods
118{
119  AcquireMemoryHandler
120    acquire_memory_handler;
121
122  ResizeMemoryHandler
123    resize_memory_handler;
124
125  DestroyMemoryHandler
126    destroy_memory_handler;
127} MagickMemoryMethods;
128
129struct _MemoryInfo
130{
131  char
132    filename[MaxTextExtent];
133
134  VirtualMemoryType
135    type;
136
137  size_t
138    length;
139
140  void
141    *blob;
142
143  size_t
144    signature;
145};
146
147typedef struct _MemoryPool
148{
149  size_t
150    allocation;
151
152  void
153    *blocks[MaxBlocks+1];
154
155  size_t
156    number_segments;
157
158  DataSegmentInfo
159    *segments[MaxSegments],
160    segment_pool[MaxSegments];
161} MemoryPool;
162
163/*
164  Global declarations.
165*/
166#if defined _MSC_VER
167static void* MSCMalloc(size_t size)
168{
169  return malloc(size);
170}
171static void* MSCRealloc(void* ptr, size_t size)
172{
173  return realloc(ptr, size);
174}
175static void MSCFree(void* ptr)
176{
177  free(ptr);
178}
179#endif
180
181static MagickMemoryMethods
182  memory_methods =
183  {
184#if defined _MSC_VER
185    (AcquireMemoryHandler) MSCMalloc,
186    (ResizeMemoryHandler) MSCRealloc,
187    (DestroyMemoryHandler) MSCFree
188#else
189    (AcquireMemoryHandler) malloc,
190    (ResizeMemoryHandler) realloc,
191    (DestroyMemoryHandler) free
192#endif
193  };
194#if defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
195static MemoryPool
196  memory_pool;
197
198static SemaphoreInfo
199  *memory_semaphore = (SemaphoreInfo *) NULL;
200
201static volatile DataSegmentInfo
202  *free_segments = (DataSegmentInfo *) NULL;
203
204/*
205  Forward declarations.
206*/
207static MagickBooleanType
208  ExpandHeap(size_t);
209#endif
210
211/*
212%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
213%                                                                             %
214%                                                                             %
215%                                                                             %
216%   A c q u i r e A l i g n e d M e m o r y                                   %
217%                                                                             %
218%                                                                             %
219%                                                                             %
220%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
221%
222%  AcquireAlignedMemory() returns a pointer to a block of memory at least size
223%  bytes whose address is a multiple of 16*sizeof(void *).
224%
225%  The format of the AcquireAlignedMemory method is:
226%
227%      void *AcquireAlignedMemory(const size_t count,const size_t quantum)
228%
229%  A description of each parameter follows:
230%
231%    o count: the number of quantum elements to allocate.
232%
233%    o quantum: the number of bytes in each quantum.
234%
235*/
236MagickExport void *AcquireAlignedMemory(const size_t count,const size_t quantum)
237{
238#define AlignedExtent(size,alignment) \
239  (((size)+((alignment)-1)) & ~((alignment)-1))
240
241  size_t
242    alignment,
243    extent,
244    size;
245
246  void
247    *memory;
248
249  size=count*quantum;
250  if ((count == 0) || (quantum != (size/count)))
251    {
252      errno=ENOMEM;
253      return((void *) NULL);
254    }
255  memory=NULL;
256  alignment=CACHE_LINE_SIZE;
257  extent=AlignedExtent(size,alignment);
258  if ((size == 0) || (alignment < sizeof(void *)) || (extent < size))
259    return((void *) NULL);
260#if defined(MAGICKCORE_HAVE_POSIX_MEMALIGN)
261  if (posix_memalign(&memory,alignment,extent) != 0)
262    memory=NULL;
263#elif defined(MAGICKCORE_HAVE__ALIGNED_MALLOC)
264  memory=_aligned_malloc(extent,alignment);
265#else
266  {
267    void
268      *p;
269
270    extent=(size+alignment-1)+sizeof(void *);
271    if (extent > size)
272      {
273        p=malloc(extent);
274        if (p != NULL)
275          {
276            memory=(void *) AlignedExtent((size_t) p+sizeof(void *),alignment);
277            *((void **) memory-1)=p;
278          }
279      }
280  }
281#endif
282  return(memory);
283}
284
285#if defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
286/*
287%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
288%                                                                             %
289%                                                                             %
290%                                                                             %
291+   A c q u i r e B l o c k                                                   %
292%                                                                             %
293%                                                                             %
294%                                                                             %
295%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
296%
297%  AcquireBlock() returns a pointer to a block of memory at least size bytes
298%  suitably aligned for any use.
299%
300%  The format of the AcquireBlock method is:
301%
302%      void *AcquireBlock(const size_t size)
303%
304%  A description of each parameter follows:
305%
306%    o size: the size of the memory in bytes to allocate.
307%
308*/
309
310static inline size_t AllocationPolicy(size_t size)
311{
312  register size_t
313    blocksize;
314
315  /*
316    The linear distribution.
317  */
318  assert(size != 0);
319  assert(size % (4*sizeof(size_t)) == 0);
320  if (size <= BlockThreshold)
321    return(size/(4*sizeof(size_t)));
322  /*
323    Check for the largest block size.
324  */
325  if (size > (size_t) (BlockThreshold*(1L << (MaxBlockExponent-1L))))
326    return(MaxBlocks-1L);
327  /*
328    Otherwise use a power of two distribution.
329  */
330  blocksize=BlockThreshold/(4*sizeof(size_t));
331  for ( ; size > BlockThreshold; size/=2)
332    blocksize++;
333  assert(blocksize > (BlockThreshold/(4*sizeof(size_t))));
334  assert(blocksize < (MaxBlocks-1L));
335  return(blocksize);
336}
337
338static inline void InsertFreeBlock(void *block,const size_t i)
339{
340  register void
341    *next,
342    *previous;
343
344  size_t
345    size;
346
347  size=SizeOfBlock(block);
348  previous=(void *) NULL;
349  next=memory_pool.blocks[i];
350  while ((next != (void *) NULL) && (SizeOfBlock(next) < size))
351  {
352    previous=next;
353    next=NextBlockInList(next);
354  }
355  PreviousBlockInList(block)=previous;
356  NextBlockInList(block)=next;
357  if (previous != (void *) NULL)
358    NextBlockInList(previous)=block;
359  else
360    memory_pool.blocks[i]=block;
361  if (next != (void *) NULL)
362    PreviousBlockInList(next)=block;
363}
364
365static inline void RemoveFreeBlock(void *block,const size_t i)
366{
367  register void
368    *next,
369    *previous;
370
371  next=NextBlockInList(block);
372  previous=PreviousBlockInList(block);
373  if (previous == (void *) NULL)
374    memory_pool.blocks[i]=next;
375  else
376    NextBlockInList(previous)=next;
377  if (next != (void *) NULL)
378    PreviousBlockInList(next)=previous;
379}
380
381static void *AcquireBlock(size_t size)
382{
383  register size_t
384    i;
385
386  register void
387    *block;
388
389  /*
390    Find free block.
391  */
392  size=(size_t) (size+sizeof(size_t)+6*sizeof(size_t)-1) & -(4U*sizeof(size_t));
393  i=AllocationPolicy(size);
394  block=memory_pool.blocks[i];
395  while ((block != (void *) NULL) && (SizeOfBlock(block) < size))
396    block=NextBlockInList(block);
397  if (block == (void *) NULL)
398    {
399      i++;
400      while (memory_pool.blocks[i] == (void *) NULL)
401        i++;
402      block=memory_pool.blocks[i];
403      if (i >= MaxBlocks)
404        return((void *) NULL);
405    }
406  assert((*BlockHeader(NextBlock(block)) & PreviousBlockBit) == 0);
407  assert(SizeOfBlock(block) >= size);
408  RemoveFreeBlock(block,AllocationPolicy(SizeOfBlock(block)));
409  if (SizeOfBlock(block) > size)
410    {
411      size_t
412        blocksize;
413
414      void
415        *next;
416
417      /*
418        Split block.
419      */
420      next=(char *) block+size;
421      blocksize=SizeOfBlock(block)-size;
422      *BlockHeader(next)=blocksize;
423      *BlockFooter(next,blocksize)=blocksize;
424      InsertFreeBlock(next,AllocationPolicy(blocksize));
425      *BlockHeader(block)=size | (*BlockHeader(block) & ~SizeMask);
426    }
427  assert(size == SizeOfBlock(block));
428  *BlockHeader(NextBlock(block))|=PreviousBlockBit;
429  memory_pool.allocation+=size;
430  return(block);
431}
432#endif
433
434/*
435%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
436%                                                                             %
437%                                                                             %
438%                                                                             %
439%   A c q u i r e M a g i c k M e m o r y                                     %
440%                                                                             %
441%                                                                             %
442%                                                                             %
443%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
444%
445%  AcquireMagickMemory() returns a pointer to a block of memory at least size
446%  bytes suitably aligned for any use.
447%
448%  The format of the AcquireMagickMemory method is:
449%
450%      void *AcquireMagickMemory(const size_t size)
451%
452%  A description of each parameter follows:
453%
454%    o size: the size of the memory in bytes to allocate.
455%
456*/
457MagickExport void *AcquireMagickMemory(const size_t size)
458{
459  register void
460    *memory;
461
462#if !defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
463  memory=memory_methods.acquire_memory_handler(size == 0 ? 1UL : size);
464#else
465  if (memory_semaphore == (SemaphoreInfo *) NULL)
466    ActivateSemaphoreInfo(&memory_semaphore);
467  if (free_segments == (DataSegmentInfo *) NULL)
468    {
469      LockSemaphoreInfo(memory_semaphore);
470      if (free_segments == (DataSegmentInfo *) NULL)
471        {
472          register ssize_t
473            i;
474
475          assert(2*sizeof(size_t) > (size_t) (~SizeMask));
476          (void) ResetMagickMemory(&memory_pool,0,sizeof(memory_pool));
477          memory_pool.allocation=SegmentSize;
478          memory_pool.blocks[MaxBlocks]=(void *) (-1);
479          for (i=0; i < MaxSegments; i++)
480          {
481            if (i != 0)
482              memory_pool.segment_pool[i].previous=
483                (&memory_pool.segment_pool[i-1]);
484            if (i != (MaxSegments-1))
485              memory_pool.segment_pool[i].next=(&memory_pool.segment_pool[i+1]);
486          }
487          free_segments=(&memory_pool.segment_pool[0]);
488        }
489      UnlockSemaphoreInfo(memory_semaphore);
490    }
491  LockSemaphoreInfo(memory_semaphore);
492  memory=AcquireBlock(size == 0 ? 1UL : size);
493  if (memory == (void *) NULL)
494    {
495      if (ExpandHeap(size == 0 ? 1UL : size) != MagickFalse)
496        memory=AcquireBlock(size == 0 ? 1UL : size);
497    }
498  UnlockSemaphoreInfo(memory_semaphore);
499#endif
500  return(memory);
501}
502
503/*
504%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
505%                                                                             %
506%                                                                             %
507%                                                                             %
508%   A c q u i r e Q u a n t u m M e m o r y                                   %
509%                                                                             %
510%                                                                             %
511%                                                                             %
512%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
513%
514%  AcquireQuantumMemory() returns a pointer to a block of memory at least
515%  count * quantum bytes suitably aligned for any use.
516%
517%  The format of the AcquireQuantumMemory method is:
518%
519%      void *AcquireQuantumMemory(const size_t count,const size_t quantum)
520%
521%  A description of each parameter follows:
522%
523%    o count: the number of quantum elements to allocate.
524%
525%    o quantum: the number of bytes in each quantum.
526%
527*/
528MagickExport void *AcquireQuantumMemory(const size_t count,const size_t quantum)
529{
530  size_t
531    size;
532
533  size=count*quantum;
534  if ((count == 0) || (quantum != (size/count)))
535    {
536      errno=ENOMEM;
537      return((void *) NULL);
538    }
539  return(AcquireMagickMemory(size));
540}
541
542/*
543%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
544%                                                                             %
545%                                                                             %
546%                                                                             %
547%   A c q u i r e V i r t u a l M e m o r y                                   %
548%                                                                             %
549%                                                                             %
550%                                                                             %
551%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
552%
553%  AcquireVirtualMemory() allocates a pointer to a block of memory at least size
554%  bytes suitably aligned for any use.
555%
556%  The format of the AcquireVirtualMemory method is:
557%
558%      MemoryInfo *AcquireVirtualMemory(const size_t count,const size_t quantum)
559%
560%  A description of each parameter follows:
561%
562%    o count: the number of quantum elements to allocate.
563%
564%    o quantum: the number of bytes in each quantum.
565%
566*/
567MagickExport MemoryInfo *AcquireVirtualMemory(const size_t count,
568  const size_t quantum)
569{
570  MemoryInfo
571    *memory_info;
572
573  size_t
574    length;
575
576  length=count*quantum;
577  if ((count == 0) || (quantum != (length/count)))
578    {
579      errno=ENOMEM;
580      return((MemoryInfo *) NULL);
581    }
582  memory_info=(MemoryInfo *) MagickAssumeAligned(AcquireAlignedMemory(1,
583    sizeof(*memory_info)));
584  if (memory_info == (MemoryInfo *) NULL)
585    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
586  (void) ResetMagickMemory(memory_info,0,sizeof(*memory_info));
587  memory_info->length=length;
588  memory_info->signature=MagickSignature;
589  if (AcquireMagickResource(MemoryResource,length) != MagickFalse)
590    {
591      memory_info->blob=AcquireAlignedMemory(1,length);
592      if (memory_info->blob != NULL)
593        memory_info->type=AlignedVirtualMemory;
594      else
595        RelinquishMagickResource(MemoryResource,length);
596    }
597  if ((memory_info->blob == NULL) &&
598      (AcquireMagickResource(MapResource,length) != MagickFalse))
599    {
600      /*
601        Heap memory failed, try anonymous memory mapping.
602      */
603      memory_info->blob=MapBlob(-1,IOMode,0,length);
604      if (memory_info->blob != NULL)
605        memory_info->type=MapVirtualMemory;
606      else
607        RelinquishMagickResource(MapResource,length);
608    }
609  if (memory_info->blob == NULL)
610    {
611      int
612        file;
613
614      /*
615        Anonymous memory mapping failed, try file-backed memory mapping.
616      */
617      file=AcquireUniqueFileResource(memory_info->filename);
618      if (file != -1)
619        {
620          if ((lseek(file,length-1,SEEK_SET) >= 0) && (write(file,"",1) == 1))
621            {
622              memory_info->blob=MapBlob(file,IOMode,0,length);
623              if (memory_info->blob != NULL)
624                {
625                  memory_info->type=MapVirtualMemory;
626                  (void) AcquireMagickResource(MapResource,length);
627                }
628            }
629          (void) close(file);
630        }
631    }
632  if (memory_info->blob == NULL)
633    {
634      memory_info->blob=AcquireMagickMemory(length);
635      if (memory_info->blob != NULL)
636        memory_info->type=UnalignedVirtualMemory;
637    }
638  if (memory_info->blob == NULL)
639    memory_info=RelinquishVirtualMemory(memory_info);
640  return(memory_info);
641}
642
643/*
644%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
645%                                                                             %
646%                                                                             %
647%                                                                             %
648%   C o p y M a g i c k M e m o r y                                           %
649%                                                                             %
650%                                                                             %
651%                                                                             %
652%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
653%
654%  CopyMagickMemory() copies size bytes from memory area source to the
655%  destination.  Copying between objects that overlap will take place
656%  correctly.  It returns destination.
657%
658%  The format of the CopyMagickMemory method is:
659%
660%      void *CopyMagickMemory(void *destination,const void *source,
661%        const size_t size)
662%
663%  A description of each parameter follows:
664%
665%    o destination: the destination.
666%
667%    o source: the source.
668%
669%    o size: the size of the memory in bytes to allocate.
670%
671*/
672MagickExport void *CopyMagickMemory(void *destination,const void *source,
673  const size_t size)
674{
675  register const unsigned char
676    *p;
677
678  register unsigned char
679    *q;
680
681  assert(destination != (void *) NULL);
682  assert(source != (const void *) NULL);
683  p=(const unsigned char *) source;
684  q=(unsigned char *) destination;
685  if (((q+size) < p) || (q > (p+size)))
686    switch (size)
687    {
688      default: return(memcpy(destination,source,size));
689      case 8: *q++=(*p++);
690      case 7: *q++=(*p++);
691      case 6: *q++=(*p++);
692      case 5: *q++=(*p++);
693      case 4: *q++=(*p++);
694      case 3: *q++=(*p++);
695      case 2: *q++=(*p++);
696      case 1: *q++=(*p++);
697      case 0: return(destination);
698    }
699  return(memmove(destination,source,size));
700}
701
702/*
703%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
704%                                                                             %
705%                                                                             %
706%                                                                             %
707+   D e s t r o y M a g i c k M e m o r y                                     %
708%                                                                             %
709%                                                                             %
710%                                                                             %
711%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
712%
713%  DestroyMagickMemory() deallocates memory associated with the memory manager.
714%
715%  The format of the DestroyMagickMemory method is:
716%
717%      DestroyMagickMemory(void)
718%
719*/
720MagickExport void DestroyMagickMemory(void)
721{
722#if defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
723  register ssize_t
724    i;
725
726  if (memory_semaphore == (SemaphoreInfo *) NULL)
727    ActivateSemaphoreInfo(&memory_semaphore);
728  LockSemaphoreInfo(memory_semaphore);
729  for (i=0; i < (ssize_t) memory_pool.number_segments; i++)
730    if (memory_pool.segments[i]->mapped == MagickFalse)
731      memory_methods.destroy_memory_handler(
732        memory_pool.segments[i]->allocation);
733    else
734      (void) UnmapBlob(memory_pool.segments[i]->allocation,
735        memory_pool.segments[i]->length);
736  free_segments=(DataSegmentInfo *) NULL;
737  (void) ResetMagickMemory(&memory_pool,0,sizeof(memory_pool));
738  UnlockSemaphoreInfo(memory_semaphore);
739  RelinquishSemaphoreInfo(&memory_semaphore);
740#endif
741}
742
743#if defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
744/*
745%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
746%                                                                             %
747%                                                                             %
748%                                                                             %
749+   E x p a n d H e a p                                                       %
750%                                                                             %
751%                                                                             %
752%                                                                             %
753%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
754%
755%  ExpandHeap() get more memory from the system.  It returns MagickTrue on
756%  success otherwise MagickFalse.
757%
758%  The format of the ExpandHeap method is:
759%
760%      MagickBooleanType ExpandHeap(size_t size)
761%
762%  A description of each parameter follows:
763%
764%    o size: the size of the memory in bytes we require.
765%
766*/
767static MagickBooleanType ExpandHeap(size_t size)
768{
769  DataSegmentInfo
770    *segment_info;
771
772  MagickBooleanType
773    mapped;
774
775  register ssize_t
776    i;
777
778  register void
779    *block;
780
781  size_t
782    blocksize;
783
784  void
785    *segment;
786
787  blocksize=((size+12*sizeof(size_t))+SegmentSize-1) & -SegmentSize;
788  assert(memory_pool.number_segments < MaxSegments);
789  segment=MapBlob(-1,IOMode,0,blocksize);
790  mapped=segment != (void *) NULL ? MagickTrue : MagickFalse;
791  if (segment == (void *) NULL)
792    segment=(void *) memory_methods.acquire_memory_handler(blocksize);
793  if (segment == (void *) NULL)
794    return(MagickFalse);
795  segment_info=(DataSegmentInfo *) free_segments;
796  free_segments=segment_info->next;
797  segment_info->mapped=mapped;
798  segment_info->length=blocksize;
799  segment_info->allocation=segment;
800  segment_info->bound=(char *) segment+blocksize;
801  i=(ssize_t) memory_pool.number_segments-1;
802  for ( ; (i >= 0) && (memory_pool.segments[i]->allocation > segment); i--)
803    memory_pool.segments[i+1]=memory_pool.segments[i];
804  memory_pool.segments[i+1]=segment_info;
805  memory_pool.number_segments++;
806  size=blocksize-12*sizeof(size_t);
807  block=(char *) segment_info->allocation+4*sizeof(size_t);
808  *BlockHeader(block)=size | PreviousBlockBit;
809  *BlockFooter(block,size)=size;
810  InsertFreeBlock(block,AllocationPolicy(size));
811  block=NextBlock(block);
812  assert(block < segment_info->bound);
813  *BlockHeader(block)=2*sizeof(size_t);
814  *BlockHeader(NextBlock(block))=PreviousBlockBit;
815  return(MagickTrue);
816}
817#endif
818
819/*
820%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
821%                                                                             %
822%                                                                             %
823%                                                                             %
824%   G e t M a g i c k M e m o r y M e t h o d s                               %
825%                                                                             %
826%                                                                             %
827%                                                                             %
828%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
829%
830%  GetMagickMemoryMethods() gets the methods to acquire, resize, and destroy
831%  memory.
832%
833%  The format of the GetMagickMemoryMethods() method is:
834%
835%      void GetMagickMemoryMethods(AcquireMemoryHandler *acquire_memory_handler,
836%        ResizeMemoryHandler *resize_memory_handler,
837%        DestroyMemoryHandler *destroy_memory_handler)
838%
839%  A description of each parameter follows:
840%
841%    o acquire_memory_handler: method to acquire memory (e.g. malloc).
842%
843%    o resize_memory_handler: method to resize memory (e.g. realloc).
844%
845%    o destroy_memory_handler: method to destroy memory (e.g. free).
846%
847*/
848MagickExport void GetMagickMemoryMethods(
849  AcquireMemoryHandler *acquire_memory_handler,
850  ResizeMemoryHandler *resize_memory_handler,
851  DestroyMemoryHandler *destroy_memory_handler)
852{
853  assert(acquire_memory_handler != (AcquireMemoryHandler *) NULL);
854  assert(resize_memory_handler != (ResizeMemoryHandler *) NULL);
855  assert(destroy_memory_handler != (DestroyMemoryHandler *) NULL);
856  *acquire_memory_handler=memory_methods.acquire_memory_handler;
857  *resize_memory_handler=memory_methods.resize_memory_handler;
858  *destroy_memory_handler=memory_methods.destroy_memory_handler;
859}
860
861/*
862%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
863%                                                                             %
864%                                                                             %
865%                                                                             %
866%   G e t V i r t u a l M e m o r y B l o b                                   %
867%                                                                             %
868%                                                                             %
869%                                                                             %
870%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
871%
872%  GetVirtualMemoryBlob() returns the virtual memory blob associated with the
873%  specified MemoryInfo structure.
874%
875%  The format of the GetVirtualMemoryBlob method is:
876%
877%      void *GetVirtualMemoryBlob(const MemoryInfo *memory_info)
878%
879%  A description of each parameter follows:
880%
881%    o memory_info: The MemoryInfo structure.
882*/
883MagickExport void *GetVirtualMemoryBlob(const MemoryInfo *memory_info)
884{
885  assert(memory_info != (const MemoryInfo *) NULL);
886  assert(memory_info->signature == MagickSignature);
887  return(memory_info->blob);
888}
889
890/*
891%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
892%                                                                             %
893%                                                                             %
894%                                                                             %
895%   R e l i n q u i s h A l i g n e d M e m o r y                             %
896%                                                                             %
897%                                                                             %
898%                                                                             %
899%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
900%
901%  RelinquishAlignedMemory() frees memory acquired with AcquireAlignedMemory()
902%  or reuse.
903%
904%  The format of the RelinquishAlignedMemory method is:
905%
906%      void *RelinquishAlignedMemory(void *memory)
907%
908%  A description of each parameter follows:
909%
910%    o memory: A pointer to a block of memory to free for reuse.
911%
912*/
913MagickExport void *RelinquishAlignedMemory(void *memory)
914{
915  if (memory == (void *) NULL)
916    return((void *) NULL);
917#if defined(MAGICKCORE_HAVE_POSIX_MEMALIGN)
918  free(memory);
919#elif defined(MAGICKCORE_HAVE__ALIGNED_MALLOC)
920  _aligned_free(memory);
921#else
922  free(*((void **) memory-1));
923#endif
924  return(NULL);
925}
926
927/*
928%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
929%                                                                             %
930%                                                                             %
931%                                                                             %
932%   R e l i n q u i s h M a g i c k M e m o r y                               %
933%                                                                             %
934%                                                                             %
935%                                                                             %
936%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
937%
938%  RelinquishMagickMemory() frees memory acquired with AcquireMagickMemory()
939%  or AcquireQuantumMemory() for reuse.
940%
941%  The format of the RelinquishMagickMemory method is:
942%
943%      void *RelinquishMagickMemory(void *memory)
944%
945%  A description of each parameter follows:
946%
947%    o memory: A pointer to a block of memory to free for reuse.
948%
949*/
950MagickExport void *RelinquishMagickMemory(void *memory)
951{
952  if (memory == (void *) NULL)
953    return((void *) NULL);
954#if !defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
955  memory_methods.destroy_memory_handler(memory);
956#else
957  LockSemaphoreInfo(memory_semaphore);
958  assert((SizeOfBlock(memory) % (4*sizeof(size_t))) == 0);
959  assert((*BlockHeader(NextBlock(memory)) & PreviousBlockBit) != 0);
960  if ((*BlockHeader(memory) & PreviousBlockBit) == 0)
961    {
962      void
963        *previous;
964
965      /*
966        Coalesce with previous adjacent block.
967      */
968      previous=PreviousBlock(memory);
969      RemoveFreeBlock(previous,AllocationPolicy(SizeOfBlock(previous)));
970      *BlockHeader(previous)=(SizeOfBlock(previous)+SizeOfBlock(memory)) |
971        (*BlockHeader(previous) & ~SizeMask);
972      memory=previous;
973    }
974  if ((*BlockHeader(NextBlock(NextBlock(memory))) & PreviousBlockBit) == 0)
975    {
976      void
977        *next;
978
979      /*
980        Coalesce with next adjacent block.
981      */
982      next=NextBlock(memory);
983      RemoveFreeBlock(next,AllocationPolicy(SizeOfBlock(next)));
984      *BlockHeader(memory)=(SizeOfBlock(memory)+SizeOfBlock(next)) |
985        (*BlockHeader(memory) & ~SizeMask);
986    }
987  *BlockFooter(memory,SizeOfBlock(memory))=SizeOfBlock(memory);
988  *BlockHeader(NextBlock(memory))&=(~PreviousBlockBit);
989  InsertFreeBlock(memory,AllocationPolicy(SizeOfBlock(memory)));
990  UnlockSemaphoreInfo(memory_semaphore);
991#endif
992  return((void *) NULL);
993}
994
995/*
996%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
997%                                                                             %
998%                                                                             %
999%                                                                             %
1000%   R e l i n q u i s h V i r t u a l M e m o r y                             %
1001%                                                                             %
1002%                                                                             %
1003%                                                                             %
1004%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1005%
1006%  RelinquishVirtualMemory() frees memory acquired with AcquireVirtualMemory().
1007%
1008%  The format of the RelinquishVirtualMemory method is:
1009%
1010%      MemoryInfo *RelinquishVirtualMemory(MemoryInfo *memory_info)
1011%
1012%  A description of each parameter follows:
1013%
1014%    o memory_info: A pointer to a block of memory to free for reuse.
1015%
1016*/
1017MagickExport MemoryInfo *RelinquishVirtualMemory(MemoryInfo *memory_info)
1018{
1019  assert(memory_info != (MemoryInfo *) NULL);
1020  assert(memory_info->signature == MagickSignature);
1021  if (memory_info->blob != (void *) NULL)
1022    switch (memory_info->type)
1023    {
1024      case AlignedVirtualMemory:
1025      {
1026        memory_info->blob=RelinquishAlignedMemory(memory_info->blob);
1027        RelinquishMagickResource(MemoryResource,memory_info->length);
1028        break;
1029      }
1030      case MapVirtualMemory:
1031      {
1032        (void) UnmapBlob(memory_info->blob,memory_info->length);
1033        memory_info->blob=NULL;
1034        RelinquishMagickResource(MapResource,memory_info->length);
1035        if (*memory_info->filename != '\0')
1036          (void) RelinquishUniqueFileResource(memory_info->filename);
1037        break;
1038      }
1039      case UnalignedVirtualMemory:
1040      default:
1041      {
1042        memory_info->blob=RelinquishMagickMemory(memory_info->blob);
1043        break;
1044      }
1045    }
1046  memory_info->signature=(~MagickSignature);
1047  memory_info=(MemoryInfo *) RelinquishAlignedMemory(memory_info);
1048  return(memory_info);
1049}
1050
1051/*
1052%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1053%                                                                             %
1054%                                                                             %
1055%                                                                             %
1056%   R e s e t M a g i c k M e m o r y                                         %
1057%                                                                             %
1058%                                                                             %
1059%                                                                             %
1060%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1061%
1062%  ResetMagickMemory() fills the first size bytes of the memory area pointed to
1063%  by memory with the constant byte c.
1064%
1065%  The format of the ResetMagickMemory method is:
1066%
1067%      void *ResetMagickMemory(void *memory,int byte,const size_t size)
1068%
1069%  A description of each parameter follows:
1070%
1071%    o memory: a pointer to a memory allocation.
1072%
1073%    o byte: set the memory to this value.
1074%
1075%    o size: size of the memory to reset.
1076%
1077*/
1078MagickExport void *ResetMagickMemory(void *memory,int byte,const size_t size)
1079{
1080  assert(memory != (void *) NULL);
1081  return(memset(memory,byte,size));
1082}
1083
1084/*
1085%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1086%                                                                             %
1087%                                                                             %
1088%                                                                             %
1089%   R e s i z e M a g i c k M e m o r y                                       %
1090%                                                                             %
1091%                                                                             %
1092%                                                                             %
1093%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1094%
1095%  ResizeMagickMemory() changes the size of the memory and returns a pointer to
1096%  the (possibly moved) block.  The contents will be unchanged up to the
1097%  lesser of the new and old sizes.
1098%
1099%  The format of the ResizeMagickMemory method is:
1100%
1101%      void *ResizeMagickMemory(void *memory,const size_t size)
1102%
1103%  A description of each parameter follows:
1104%
1105%    o memory: A pointer to a memory allocation.
1106%
1107%    o size: the new size of the allocated memory.
1108%
1109*/
1110
1111#if defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
1112static inline void *ResizeBlock(void *block,size_t size)
1113{
1114  register void
1115    *memory;
1116
1117  if (block == (void *) NULL)
1118    return(AcquireBlock(size));
1119  memory=AcquireBlock(size);
1120  if (memory == (void *) NULL)
1121    return((void *) NULL);
1122  if (size <= (SizeOfBlock(block)-sizeof(size_t)))
1123    (void) memcpy(memory,block,size);
1124  else
1125    (void) memcpy(memory,block,SizeOfBlock(block)-sizeof(size_t));
1126  memory_pool.allocation+=size;
1127  return(memory);
1128}
1129#endif
1130
1131MagickExport void *ResizeMagickMemory(void *memory,const size_t size)
1132{
1133  register void
1134    *block;
1135
1136  if (memory == (void *) NULL)
1137    return(AcquireMagickMemory(size));
1138#if !defined(MAGICKCORE_ZERO_CONFIGURATION_SUPPORT)
1139  block=memory_methods.resize_memory_handler(memory,size == 0 ? 1UL : size);
1140  if (block == (void *) NULL)
1141    memory=RelinquishMagickMemory(memory);
1142#else
1143  LockSemaphoreInfo(memory_semaphore);
1144  block=ResizeBlock(memory,size == 0 ? 1UL : size);
1145  if (block == (void *) NULL)
1146    {
1147      if (ExpandHeap(size == 0 ? 1UL : size) == MagickFalse)
1148        {
1149          UnlockSemaphoreInfo(memory_semaphore);
1150          memory=RelinquishMagickMemory(memory);
1151          ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1152        }
1153      block=ResizeBlock(memory,size == 0 ? 1UL : size);
1154      assert(block != (void *) NULL);
1155    }
1156  UnlockSemaphoreInfo(memory_semaphore);
1157  memory=RelinquishMagickMemory(memory);
1158#endif
1159  return(block);
1160}
1161
1162/*
1163%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1164%                                                                             %
1165%                                                                             %
1166%                                                                             %
1167%   R e s i z e Q u a n t u m M e m o r y                                     %
1168%                                                                             %
1169%                                                                             %
1170%                                                                             %
1171%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1172%
1173%  ResizeQuantumMemory() changes the size of the memory and returns a pointer
1174%  to the (possibly moved) block.  The contents will be unchanged up to the
1175%  lesser of the new and old sizes.
1176%
1177%  The format of the ResizeQuantumMemory method is:
1178%
1179%      void *ResizeQuantumMemory(void *memory,const size_t count,
1180%        const size_t quantum)
1181%
1182%  A description of each parameter follows:
1183%
1184%    o memory: A pointer to a memory allocation.
1185%
1186%    o count: the number of quantum elements to allocate.
1187%
1188%    o quantum: the number of bytes in each quantum.
1189%
1190*/
1191MagickExport void *ResizeQuantumMemory(void *memory,const size_t count,
1192  const size_t quantum)
1193{
1194  size_t
1195    size;
1196
1197  size=count*quantum;
1198  if ((count == 0) || (quantum != (size/count)))
1199    {
1200      memory=RelinquishMagickMemory(memory);
1201      errno=ENOMEM;
1202      return((void *) NULL);
1203    }
1204  return(ResizeMagickMemory(memory,size));
1205}
1206
1207/*
1208%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1209%                                                                             %
1210%                                                                             %
1211%                                                                             %
1212%   S e t M a g i c k M e m o r y M e t h o d s                               %
1213%                                                                             %
1214%                                                                             %
1215%                                                                             %
1216%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1217%
1218%  SetMagickMemoryMethods() sets the methods to acquire, resize, and destroy
1219%  memory. Your custom memory methods must be set prior to the
1220%  MagickCoreGenesis() method.
1221%
1222%  The format of the SetMagickMemoryMethods() method is:
1223%
1224%      SetMagickMemoryMethods(AcquireMemoryHandler acquire_memory_handler,
1225%        ResizeMemoryHandler resize_memory_handler,
1226%        DestroyMemoryHandler destroy_memory_handler)
1227%
1228%  A description of each parameter follows:
1229%
1230%    o acquire_memory_handler: method to acquire memory (e.g. malloc).
1231%
1232%    o resize_memory_handler: method to resize memory (e.g. realloc).
1233%
1234%    o destroy_memory_handler: method to destroy memory (e.g. free).
1235%
1236*/
1237MagickExport void SetMagickMemoryMethods(
1238  AcquireMemoryHandler acquire_memory_handler,
1239  ResizeMemoryHandler resize_memory_handler,
1240  DestroyMemoryHandler destroy_memory_handler)
1241{
1242  /*
1243    Set memory methods.
1244  */
1245  if (acquire_memory_handler != (AcquireMemoryHandler) NULL)
1246    memory_methods.acquire_memory_handler=acquire_memory_handler;
1247  if (resize_memory_handler != (ResizeMemoryHandler) NULL)
1248    memory_methods.resize_memory_handler=resize_memory_handler;
1249  if (destroy_memory_handler != (DestroyMemoryHandler) NULL)
1250    memory_methods.destroy_memory_handler=destroy_memory_handler;
1251}
1252