��������� ������������� ���������� �������
|
����� ���� �������� ���������� ������ �
������� ����� � ����������� �� ��� ������������ ����� ����������.
����� �������, �������� ������� ����������� ������ ������� �����,
�����-�� ����� ����� ������ �� ����� � ������� ������ ���.
�. �������� |
��� ������������ ��������� ������ �������
�� ��������� ������ ����������� �� ����� ���������� ������. ������������
���������, ����� �������, ������������������� ������������,
����� ������� ����������� �� ����� ���������� ���������. � �������� �����,
� ��, � ������ ������� ������� �������������� ����� � ��� �� ����������
��������� ������ � ���� ��. �� �� ������ ������� ����������� ���������
����� ����������� ������� ����� �������� ���������, ��� ������������.
������� ��������� ����� � ���, ��� ��� ����������� ��������� ������� ��������������
� � ������� ����� ��������� � ����������� ���������� �� ����� ����������
������. ��� ������������ �� ������������� ����� ��������� ������������
����������� ������������ �� ����������� ������ ���, ����� �������������
������ ����� �������������� ��� �������������� ����������� ��������. �����
�������, ������������ �������������� ������ ������� ������� ����� �������
� ��������� ������� (������� ���������� � ������� ������� ������������
�������������) �������� ������� ������ �������� ��������� �������� ���������
������, ���������� ����� ��� �����.
������ ������������������ �������� ������ � ������� �� ��� ����� ��������
� ����, ��� ��� ��������� ������ ����� ������� �� ����� ���������� �������,
� ������� ��������� �������� ����� ���������� ��������, ���� ���� �����
���� ��������� ��������� ������ ������� ������ ���������. ��� �������
���������� ������������� ������ (���. 4.3).
������ ���������� ����� ������ ������ � ������� ������������
(��� ����� ���������� ������������ ����� ���������� �����). ����� ����,
������� ���������� ������ ������� ����������� ������. ���������� �����
����� ������ ���������� ������� ����. � �������, ������������ ����������
��������� ������������� ������ ��� ����� � ������� ����� ������� ��� ����������
�������.
� ����������� �� �������� ������ ������������ ��������� ��������� ������
��������� ������ ������. ��������, ��������� ����� �������� ����� �����������
������� ��� ���������� ������������� ��������. ��� ������ ��������� �������
����� �������������� � ������ ��������� �������� ���.
�������� ��������, ����� ����� ������������� � �������, �������� ����,
� ������� ��� ����������. ��� ��������� ������ ��������� ������ � �����-���
���������, �. �. ����������, ��������� � �������� ����������� �������
����� ������� � ��������� �������.
�������� ����� ��������, ����� ��������� �� ������� ������ ����� �����������
�� ������ � ����� ���� ����������� ��������� ��������������
������, ����������� ������� ������ ������ � ����� ���������� ���������
�������. ��������, ������� realloc() � ������
����������� ������� UNIX ����� ���� ������������ ������ ��� ���� ����.

���. 4.3. ������� ������������
� ����������� ������������ �������� ������ �������� ������, ����� ���
malloc/free/realloc � �, new/dispose
� Pascal � �. �., ��� �������, ������������ ���������, ������������ ��
�������� ����� ������: ��������� ����������� ����� ���������� �������
� ��������� ������� � ����������� �� ����� ��������� �������.
�������, ��������� ������� � ������ �� ������ �������. ���� �� ���� �������
��������� ���������� �����, �������� ����� ��������� ���������, �������
"�������� �����" ������ ���������������� ���������� (������
4.2).
������ 4.2. ������ ������������������ ��������
������
while(TRUE) {
void * bl = malloc(random (10)); /* ��������� ������ �� 0 �� 10 ���� */
void * �2 = malloc(random(lO)+10); � ........ �� 10 �� 20 ���� */
if(� == NULL && �2 == NULL) /* ���� ������ ��� */
break; /* ����� �� ����� */
free(b1);
void * �� = malloc(150);
/* ������ �����, ������ �� ����� �������� */
� ���������� ���������� ����� ��������� ��� ��������� ������ ����� "��������
�� �����": ����� ������ ����� ���������� ������� ����� �������� �������
���� �������� ������� (���. 4.4)

���. 4.4. ��������� ������ ��������� ������� 4.2
� �������, ������ 4.2 ����� ������������� ��������. � �������� ����������
����� �������� ����������� �����, � ����� ����������� ����� ���������
���������, ��� ������� ��������� � ������������� �������� ���������� �����.
����������� ������ �������� �� ��� �������������, ��� ������� ��������
��� ����� ������, ������ ������� ������������� ������������ � ���������
�� �����. ���� �� ����������� ������� ��������� ����� 32 ������, �������
������� ������������ ��� ������ �� �������: �� ������ ������ ����� ����������
���� ����. �� ��� ���� �� ���������� � �������� ���������, ������� ����������
���������� �������������: ���� ������� ����� �������� ������ �����, �������
32 ������, � ��� ������� ����� 15 ��� 47 ����, �� 17 ���� �� ���� ��������
�������� (���. 4.5).

���. 4.5. ���������� ������������
��� ������ ������ ������� ���������, ��� ������ ��� ������ ������������
�������, � ��� ������� ������ ������������ ������������ ����������. ��������
������ ������� �� �������� ������� �������������� �����. ������ ������
��������������� � ���, ��� � ������ ����� � ������� �������� ��������
������� ���������, �. �. ��������� ������� ������ � ���������� ����� ,
��� N� ���������� ���������� ������, s� ������ ������� ���������, �
� ������� ������ �����. �������� ��� �������, �� ������� ��������� ���
�������� ������: ,�. �. ������ ������� ������ � �����������
������� ������� ���������.
���� ������� ������ ����� ������� � �������� ���������, ���� ������� ������
��������, �� ��� ����� ���� ������� ������ ������� �������� ������. ���,
���� s = , ���� ������� ���� 50% ������, ��� ������
����������� �� ������� �������: ���� ������������� ���� ���� ������ ����������
����������, �������� ������ ��� "����"; ���� ���� �� ���� �������,
�� ��� ���� ��������� ��� ����������� �����, ���� �� ������� ��������
����� ����. ������ �������� ������ ������������ �������������� �������������
������ �� �����, �� �� ������������ �������� ����� ������ ������� �����������
��������.
�������� ���������� ������������� ������ ������������� ��� � 50-� ����.
����� ������������ �������� ���� �������� ��������� � [���� 2000] � ������
������ ���������.
������ ��� ��������� ����� ������ ������������ � ��������������� ���������
������. ������ ������ ���� ��������������� ��� ����, ����� �� ���� � �����
������ ����� ���� ������� ����� ����. �������, ���� ��� �������� �� ����������
����� ������������ ����� ������, �� ����� ������ ��������� ��������� ������
� ������ ��������� ��������� �� ���������� ����. ��� ������ �������� ����������
� ����� ������������ ���������������� �������. ���� ������ � ���, ���
������ ��������� ��� ����������� ��������� ������ ��������� �� �� ������
� ������������ � �������, ������� ��� ����� ���������� ���������������
������ ����� ���������.
����� � ������ ����� ������� ����� ���������: �� ���������� �������
����������� (first fit) �����, �� �����, ������ �������� �����
����� � ��������� � �������� ����������� (best fit),
�, �������, �� ���������� ������ �������� �����, ��������
����������� (worst fit).
������������� ��������� worst fit ����� ����� ����� ��� � ��������� �
����������� ������ �� �������� �������. ��� ����� �������� ��������� ������
(������ ������� ������ ����, � ���� �� ������������ �����, �� � ������
�������� ����� ��������, ��� ��������� ������ ���), �� ������� ��������
��� ������������ ������: ����� ������� � ��������������� ������ ���������������
� (n), ��� n �
������ ������.
�������� ����� � ��������������� ������ ��� ���� � ����� ������� ����������
� (n + log(n)) � ���������� ����������� ��
���������� ������. ������������� ���-������ ��� �������� �������� �������
��������� �������� � ���������� ���������, ������� ���� � ����� �� �����������.
�� �������� ��������� worst fit ������������ ��� ���������� ������������
� �������� ��������, �������� � HPFS, �� �� ������ ������� �� �������������
��� ������������� ����������� ������ ������ ����������.
���� ����� ��������� ��������������� ������. ��� ���������� �������� �����������
�� ������� ������������� ���� ������, � �� ����� ��� ������ ����������
����� ��������� � ����� �����, � ������� ����� ������ ����� ������. ���������
������ � ������� �� ��������� ���������� ���������� ������ � ������ ����������.
(��������, �������� � ������� �����������, ����� �������������� ���������
��� �����������.)
� ����� ������ best fit ����������� ������������
������. �������������, ���� �� ����� ���� � �������� ������ ���������,
�� ������ �������� "�����" � �������� ��� ��� ����� ���������
����. �������, ��� � ������ best fit �������
������ ����� "������" ����� ���������, � �� � ����� �������
������� ���������� ������ ������, ������� ���������� ����������, ��� ���
������������ ����� ���� ������.
� ��� ���������, ����� �� ��������� ����� ���������� ������������� ��������,
���� ���������� ���� �� ������ � ��������� best fit ����� ��������� �����������.
������ ���������� ������������� ������ ������������ �� ����� ������, �
� ��� ������ ������������ ��������� first fit.
��� ������������� first fit � �������� ��������������� ������� ���������
������������� ��������. ���� ������ ��� ������������� ������ � ������
� ���� �� �����, �� ������� �����, ������������� ����� � ������, �����
���� ���������. ��������������, ������ ����� ����� ������������ � ������
������, ��� �������� ������� ����� ������ (���. 4.6). ������� ������ ������
� ���� �������� ������� � ���, ����� ������������� ������ �� � ����� �����������,
�� � ������. ����� ����������� � ��� ����� ������� ����� ����������� �
���������: ������ �������� ���������, � ������ ����� ���������� � ����
�����, ��� �� ������������ � ������� ���. � ��� �� ����� ����������� ��������������
�����. � ���������� ������ ����� ���������� �������������� � ������� "��������������"
�� ���������.
���. 4.6. ��������������
����������� ��������� ������������� ������������� ������ ������ ������
��� ���� ������ ��������, � ������ � ����������� ��������� ������. �������������,
������, ���� �� ����� ��� ��������� ������ �� ������ ��������� � �� �����
������� �� ��� ���� ���� � 100 ��������. �� ���� ��� ��� ����� �����������
� ������ ���� �� ������, � �� �� ����� �� ��� ���� ���������� � ��� ������
�����������.
����� ����, ���� �� ����� ���������� ����� � �����, ��� ������������ ����
��������� ������ ��������� brkievel, �� �� �����,
������ ��������� ����� ����� � ������, ������ ��������� �������� brkievel
�, ����� �������, ������� �������� ������ �������.
���������� ���� ��� ������, ��� ���, ��� �� ����� � �����, � ��� ��� ���������
����� � ������. ����� ������, ��� ��� ����� ������ ��������. �������������,
��� ����������� ����� � �������� �� ������ ����� �� � ������ ���������,
��� �� ���������, ��� ��� �� ���. ��� ����� �� ������ ����������� ����
������. ��� ���� �� ���� ��������� ������ ����� ��������� �����������
����������� ������ ��������� ������ �� ������.
������� ����� ���������� � ����������� ����� ��������� �� �����������
�������� ������. ������� ������ ��� ����, �� �������� � ������, �������
���������� ���������� ������ ����� � �������
� ���, ��� �� ��������� � ������� ����� �� ��� ����� ������. ������ �����,
� �� �����. ���� � ���, ��� ��������� �������� ���������� �����, �����
������� � ��� ������ ����� � ������ ��� ������. ������ ����� ����� ��������
������� �� �����, ������� � �����, � ������ ����� ������ ����� �������
������. �� �86 � �������� ������ ��� �� ���, �� ��� ������ �������� ��������
���������.
����, �� ��������� � ����� ��� ����� � ���� ����� ���, ������ ����� ����.
� ��� ����� �� ���������� ������ �����. ���������� ������������ ����������,
������� �������� ����. ��� ���� �� �������������, ��� �������� ���� �����
��������������, ���� ���� ��������, � ��������������, ���� ���� �����.
����� ������� � ��������, ����� ������ ����� ��������� ��� ����������
(���. 4.7).
����������, ��� �� ����������� ���� � ������� addr.
�������, ��� addr �����
��� word *, � ��� ���������� � ���� ����� �����
�������������� ����� ����� ������������� � ������, ��� � ����� �. ���
���� ����� ���������, �������� �� ����� ����� ���, �� ������ ����������
����� � ������� addr 2. ���� ��� ������������,
�� ����� �����, � �� ������ �������� ��� � ����� (���. 4.8). ���� �� ���
������������, �� �� ����� ����� ���������� ����� ������ ����� ����� ���
addr - addr[-2].
��������� ����� ������ �����, �� ����� ����� ���������� ���� ���� � ������
addr, ��� ����� ������ ������� �������� �����-������������
� �������� �� � ����������� ������ �������� �����. ��� ���� �� ����� �����
��������� ������������� ���� � ������ � ��������� ������ ��� ������!

���. 4.7. ������ �����
������� ������� �������������� � �����, ������� ����� ����. ������������
������� ������� � ���, ��� ����� ������ ���-���� ����� ��������� �� ������
��������� ������.
����������, ������ ����� ����� ������������� ��� ������ ���������� �������,
������������� ���� ��� ���� �� ���� ��������� ������: ����������������
������, ����������� � ���� ��� �������, ��� � ��������� �����, � ����������������
�� ������. �������������� ������������ ������������ ��������� �������
� ���, ��� �� ����� ����������� ����� ������, ��� ������������ ������������
������ �����, ������ � ������ �� �������� ����� � ������ ���� ���������
� ��� �������������� �����. �������������, �� � ����� ������ ����� ���������
��� ������� ������ ������ � ��������� � ���, ��� ��� ��������� ����� �����
� ������, ��� � ��� ����� ������ ��������� �����, ��� ���� ������� � ������
�� ��������� � �. �.

���. 4.8. ����������� � �������������� ������ �����
����������
��� ������������� ������� ������������, ��� ��� ��� ����������� ���������
��������� ������ ������ � �����������, � ������� � ����������� �� Zortech
C/C++ �������, ��� "������� ������������, ������� ��� ����� [ ������
������ � ����������� � ����. ���.], �������� � �������� ��� ����"
([Zortech v3.xj).
����, ��������� �� ��������� ������������� ���������� �������������
������������� ������ �������� �������� ������ �����
� ������������ ��������� ������ � ��������������� ��������� ������
� ������� �� �������� first fit. ���� �������� ������������ ����������
������������������ ����� ��� ���� ��������� ������������� ������, ������������
� ���������� ����������.
�������� ������ ����� ��� ��������� ��������� ������ � ������ 60-�. �
������� ������� ������������ ����� [����, 2000], ���� �������� ����������
��� ��������� "������������ � ������������� ������". � �����������
�������� ������������ � ����� ������� ��������� ������������, �� ������
�������� ������ ���������� ����� ������� ����� �� ��������� ���' ���������
�� ������������� �����. � ���� ������, ����������� ��� ����������� ������������
������������� ��������� ������ (� ���������, ���������� ����������� ����������
����� �) ���������� ������� ��������� ������ �����. ������ ��������� �������
���� ������ ����, ��� ����, ���� ��������� ���� ������������ ������ �
����������� �������.
���������� maiioc � ���������� GNU LibC (����������
����������� ���-������ ����� � � ������ freeware ������� GNU Not Unix)
(������ 4.3) ���������� ��������� ���������: ����� �������� ����� 4096
���� ���������� ���������� first fit �� ����������� ���������� ������
� �������������� ����������� ���������, � ������������� ��� ������ ������,
������� � �������� ����� ������ ����� �� �������� ������ �����. ��� ����������
������� ����� ����� ����� ������, ������� 4096 ������.
����� �������� ������� ������������ � ������� � ���������, �����������������
�������� ������, ��� � ��������� ����� ��������� ���������. �������� ����
�������� ���������� ����������� (���. 4.9). � ������� �� ��������� ���������,
�� �� ���������� ��� ������������ ������ ���������. ������ �����, �� ���������
4-������������ ���� �� ��������� ����������� �������. ����, ��������,
���� ��������� ������� ������� �� 514 � 296 ���� ������, �� ����� ��������
��������� � 1024 � 512 ���� ��������������. ��� ��� ��������� ����� ��������
������ ����� � 4 ���������, � ������ ��� ����� �������� �� ������ ���������.
��� ����������� �������� �� ��������� ������ �� ������� ����� ��������������
��������� ��������� ���� ������. ���� ���� �� ���� �������� ����� �����,
���� ���� ��������� �������. ����� �� ������������� ��������� ��������,
���� ������������ � ���.
��������� ������ �������� �� ������ � ������ �������, � � ��������� ������������
������� _heapihfo. ��������� ��������� �� ��
����������� ������������������ ��������� ������, � �� ������ 4096 ����
������ (� ������� 4.3 ������ ��� �������� ��������� ���������
BLOCKSIZE). ��������� ����� �� ����� ��������� ������ ���������
� _heapinfo, ������ �������� �� 4096 ��������
�������������� ����� �� ������ ����.
��� ������������������� ������ ��������� ������ ��������� (�����-��������)
� ������ ������������ �������, � �������� ����������� ����. ���������
�����, ��� � � ��������� ������ �����, �� ����� ����� ����� ������� ��������������
������� ������ � ���������� �� � ������� ����������� �������.
��� ����������������� ������ ��������� ������ ������ ���������, �������
������� ���������� � ������ ���������. ����� ����, ��� ��������� ���������
������ ������� ���������� � ����� ������ � ��������� ����
������� ������� � ������ _f raghead.
������������ ��������� ������ �������� ������ �����, ��� ����������� �
������������ ��������� ������ �����, �� ��������� ����� ������ ���������
������ � ������� ����� ����� ������� ������������������. ������� o����
�����, ����������� ������������ ����������� ��� �� ������ ����������,
���������� ������� �����������, ������� � ����������� �����-�� ���������
��������� �������� ������ ����������� �������.

���. 4.9. ��������� � ���������� malloc �� GNU LibC
������ 4.3. ���������� malloc/f���
� GNU LibC. �������__default_morecore
��������� � ������� 4.1.
malloc.�
/* �������������� ������ 'malloc'.
Copyright 1990, 1991, 1992 Free Software Foundation �������� � ��� 1989
Mike Haertel.
GNU � Library �������� ��������� ����������� ������������;
�� ������ ���������� ������ ����� �/��� �������������� �� � ������������
� ����������� GNU General Public License ������ 2 ��� (�� ������ ������)
����� ����� ������� ������.
���������� GNU � ���������������� � �������, ��� ��� ����� �������, ��
��� �����-���� ��������; ���� ��� ������ �������������� ��������
������������ �������� ��� ����������� ��� ���������� ����.
��������� ��. GNU General Public License.
�� ������ ���� �������� ����� GNU General Public License ������ �
GNU � Library; ��. ���� COPYING. ���� �� �� �� ��������, �������� �� ������:
Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
� ������� ����� ��������� �� ����������� ����� �� ������ mike@ai.rait.edu,
��� Mike Haertel �/� Free Software Foundation. */
# ifndef _MALLOC_INTERNAL
#define _MALLOC_INTERNAL tinclude <malloc.h>
#endif
#ifdef __ELF_
ipragma weak malloc = __libc_malloc
#endif
/* ��� ������������� �������� �������������� ������. */
__ptr_t (*__morecore) __� ((ptrdiff_t __size))
= __default_morecore_init;
/* ��������������� ������������� ���������� ������� (hook) ��� xmalloc'
*/
void (*__malloc_initialize_hook) __P ((void));
__ptr_t (*_malloc_hook) __P ((size_t __size)) ;
/* ��������� �� ��������� ������� �����. */ char *_heapbase;
* ������� �������������� ������� � ������. �����������
����� align/__free (�� malloc/free). */
malloc_info *_heapinfo;
/* ���������� �������������� �������. */ static size_t heapsize;
/* ������ ������ � �������������� �������. */ size_t _heapindex;
/* ������������ ���������� �������� � �������������� ������� */ size_t
_heaplimit;
#if 1 /* Adapted from Mike */
/* ������� ������� ������, ����������� ��� ������� �� ��������
����������. */
int _fragblocks[BLOCKLOG];
#endif
/* ������ ��������� ���������� �� ��������.
*/ struct list _fraghead[BLOCKLOG];
/* ���������������� ����������.
*/ size_t __chunks_used; size_t _bytes_used; size_t _chunks_free; size_t
_bytes_free;
/* ����� �� �� ����? */
/* Are you experienced? */
int malloc initialized;
/* ����������� ����������. */
static __ptr_t align __P ((size_t));
static __ptr_t
align (size)
size_t size; {
__ptr_t result;
unsigned long int adj;
[result = (*__morecore) (size);
adj = (unsigned long int) ((unsigned long int) ((char *) result -
(char *) NULL)) % BLOCKSIZE; lit (adj != 0)
{
adj = BLOCKSIZE - adj; (void) (*_morecore) (adj); result = (char *) result
+ adj;
}
return result;
/* ��������� ��� � ���������, ��� � ��� ����. */
/* Set everything up and remember that we have.
*/ static int initialize _ P ( (void) ) ; static int initialize ()
{ if ( malloc initialize hook)
(*__malloc_initialize_hook) ();
heaps ize = HEAP / BLOCKSIZE;
_heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info) ) ;
if (_heapinfo == NULL)
return 0;
memset (_heapinfo, 0, heapsize * sizeof (malloc_info) ) ; _heapinfo [0]
. f ree. size = 0;
_heapinfo[0] .free. next = _heapinfo[0] . free.prev = 0; _heapindex =
0;
_heapbase = (char *) _heapinfo; __malloc_initialized = 1; return 1;
/* �������� ����������� ������, �������������
��� ��������� ������� ���������� ���� �� ���� �������������. static _
ptr_t morecore _ P ( (size_t) ) ; static _ ptr_t ,�������� (size)
size_t size;
_ ptr_t result;
malloc_info *newinfo, *oldinfo;
size_t newsize;
result = align (size) ; if (result == NULL) return NULL;
/* ���������, ����� �� ��� ��������� ������� ����������. */ if ((size_t)
BLOCK ((char *) result + size) > heapsize) I
newsize = heapsize;
while ( (size_t) BLOCK ((char *) result + size) > newsize)
newsize *= 2;
newinfo = (malloc_info *) align (newsize * sizeof (malloc_info) ) if (newinfo
== NULL) {
(* _ morecore) (-size); return NULL; }
memset (newinfo, 0, newsize * sizeof (malloc_info) ) ; memcpy (newinfo,
_heapinfo, heapsize * sizeof (malloc_info) ) ; oldinfo = _heapinfo;
newinfo[BLOCK (oldinfo) ] .busy. type = 0; newinfo [BLOCK (oldinfo) ]
.busy. info. size
= BLOCKIFY (heapsize * sizeof (malloc_info) ) ; _heapinfo = newinfo; _free_internal
(oldinfo) ; heapsize = newsize;
_heaplimit = BLOCK ((char *) result + size) ; return result; I
/* �������� ������ �� ����. */ ptr t
����� 4. ���������� �����������
libcjnalloc (size) size_t size;
I
ptr_t result;
size t block, blocks, lastblocks, start; register size_t i; struct list
*next;
/* ��������� ��������� �������� malloc (0) . �� ��� ���������. */
lif �
if (size == 0)
return NULL; #endif
if (! malloc initialized) if ( '.initialize () ) return NULL;
if ( _ malloc_hook != NULL)
return (*__malloc_hook) (size) ;
if (size < sizeof (struct list) ) size = sizeof (struct list) ;
/* ���������� �������� ���������� �� ��������� ������� �������. */ if
(size <= BLOCKSIZE / 2) {
/* ��������� ������� �������� �������� �����.
���������� �������� �������� ������� ���������.
*/ register size_t log = 1; � size; while ( (size /= 2) != 0)
/* ����������� ������ ���������� �� ������� ����������
��������� ��������� �������. */ next = _f raghead[ log] .next; if (next
!= NULL)
I
�������� � ������������ �������
/* ������� ��������� ��������� ����� �������.
���������� �������� �� ������ ���������� � ������� ���. �������� ��������
����� nfree � first.
*/ result = ( _ ptr_t) next; next->prev->next = next->next; if
(next->next != NULL)
next->next->prev = next->prev; block = BLOCK (result); if
( � _heapinf � [block] .busy. info. frag. nfree != 0)
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) next->next � (char *) NULL) % BLOCKSIZE)
� log;
/* �������� ����������. */
++_chunks_used;
_bytes_used += 1 � log;
--_chunks_f ree ;
_bytes_free -= 1 � log; t
else
/* ��� ��������� ���������� ��������� �������. ������� ����� ����� ����;
�������� ��� �� ��������� � ������� ������. */ result = _ libc_malloc
(BLOCKSIZE) ; if (result == NULL)
return NULL; #if 1 /* Adapted from Mike */
++_fragblocks [log] ; #endif
/* ������� ��� ���������, ����� �������, � ������ ���������. */ for (i
= 1; i < (size_t) (BLOCKSIZE � log); ++i) I
next = (struct list *) ((char *) result + (i � log)); next->next =
_fraghead[log] .next; next->prev = &_fraghead[log] ; next->prev->next
= next; if (next->next != NULL) next->next->prev = next;
}
/* ���������������� �������� nfree � first ��� ����� �����. */ block =
BLOCK (result); _heapinf�[block].busy.type = log;
_heapinf�[block].busy.info.frag.nfree = i � I; heapinfo[block].busy.info.frag.first
= i � 1;
_chunks_free += (BLOCKSIZE � log) - 1;
_bytes_free += BLOCKSIZE - (1 � log); _bytes_used -= BLOCKSIZE - (1 �
log);
} else
{
/* ������� ������� �������� ���� ��� ������ ������.
����������� ������ ��������� ����������, ������� � �����, ��� �� ����
� ��������� ���. ���� �� ������� ������ ����, �� ��������� ����������
�������� �����, �� ������ ����� ��������� ��� ������ � �������. */
blocks = BLOCKIFY (size);
start = block = _heapindex;
while (_heapinf�[block].free.size < blocks)
block = _heapinf�[block].free.next; if (block == start)
/* ���������� ����� ������ [������] � �������.
���������, �� ����� �� ����� ������ ������������ ���������� ����������
�����; ���� ��� ���, ��� �� ���� ����� ����������� ��� �����.
*/ block = _heapinfo[0].free.prev; lastblocks = _heapinf�[block].free.size;
if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
(*__morecore) (0) == ADDRESS (block + lastblocks) &&
(morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL)
tif 1
/* Adapted from Mike */ �
�������� ��������, ��� morecore() ����� ��������
� ������� � ������������ �������
��������� ���������� �����, ���� ��� ���������� ������� ������������ �
������ ����� ������� ��������� � ��������� ������. */ block = _heapinfo[0].free.prev;
_heapinf�[block].free.size += blocks � lastblocks; #else
_heapinf�[block].free.size = blocks; tendif
_bytes_free += (blocks - lastblocks) * BLOCKSIZE; continue; }
result = raorecore (blocks * BLOCKSIZE); if (result == NULL)
return NULL; block = BLOCK (result);
_heapinf�[block].busy.type = 0; _heapinfo[block].busy.info.size = blocks;
++ chunks used;
_bytes_used += blocks * BLOCKSIZE; return result;
/* � ���� ����� �� [��� ��� �����] ����� ���������� ������ � ������ ���������.
������, ��� ������� ��, ��� ��� �����, �� ������. */ result = ADDRESS
(block); if (_heapinf�[block].free.size > blocks) {
/* ����, ������� �� �����, ����� ��������� �������,
��� ��� ������������ ��� ������ ����� � ������ ���������. */ _heapinf�[block
+ blocks].free.size
= _heapinfo[block].free.size - blocks; _heapinfo[block + blocks].free.next
= _heapinf�[block].free.next; _heapinfo[block + blocks].free.prev
= _heapinf�[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next = _heapinfo[_heapinfo[block].free.next].free.prev
= _heapindex = block + blocks
else
I^H
/* ���� ����� ������������� ������ �������, �������
������ ������� ��� �� ������. */ _heapinfo[_heapinfo[block] .free. next]
.free.prev
= _heapinf � [block] . free.prev; _heapinfo[_heapinfo[block] .free.prev]
.free. next
= _heapindex = _heapinf � [block] . free. next; � chunksf ree ;
_heapinf � [block] .busy. type = 0;
_heapinf � [block] .busy . info. size = blocks;
++_chunks_used;
_bytes_used += blocks * BLOCKSIZE;
_bytes_free -= blocks * BLOCKSIZE;
return result;
free. c:
/* ���������� ���� ������, ���������� "malloc1.
Copyright 1990, 1991, 1992 Free Software Foundation �������� � ��� 1989
Mike Haertel.
GNU � Library �������� ��������� ����������� ������������; �� ������ ������������������
�� �/��� �������������� �� � ������������ � ����������� GNU General Public
License ������ 2 ��� (�� ������ ������) ����� ����� ������� ������.
���������� GNU � ���������������� � �������, ��� ��� ����� �������, ��
��� �����-���� ��������; ���� ��� ������ �������������� ��������
������������ �������� ��� ����������� ��� ���������� ����.
��������� ��. GNU General Public License.
� ������� ����� ��������� �� ����������� ����� �� ������ mike@ai.mit.edu,
��� Mike Haertel �/� Free Software Foundation. */
#ifndef _MALLOC_INTERNAL #define _MALLOC_INTERNAL tinclude <malloc.h>
tendif
#ifdef __ELF_
tpragma weak free = __libc_free
#endif
/^��������������� ������������� ���������� ������� (hook) ��� 4free'.
*/ void (*__free_hook) __P ((__ptr_t __ptr));
/* ������ ������, ���������� memalign. */ struct alignlist *_aligned_blocks
= NULL;
/* ������� ������ � ����. ���������� 'free' �� �� ��������
__free_hook ���� ���� �� ���������. */
void _free_internal (ptr)
__ptr_t ptr;
{
int type;
size_t block, blocks;
register size_t i;
struct list *prev, *next;
block = BLOCK (ptr);
type = _heapinf�[block].busy.type; switch (type) { case 0:
/* ������� ��� ����� ������ ���������� ��� ����� ������. */ � chunks used;
-I�----
_bytes_used -= heapinfo [block] .busy. info. size * BLOCKSIZE; bytes_free
+= heapinfo [block] .busy. info. size * BLOCKSIZE;
/* ����� ��������� �������, �������������� ����� � ������ ��������� .
������ ����� � ���������� �����, � �������� ���� ���������. ��� �����
���� ������������� ��� ��������, � ������� ��������� ���������. */ i =
_heapindex; if (i > block)
while (i > block)
i = _heapinfo[i) . free.prev; else { do
i = __heapinfo[i] . free. next; while (i > 0 && i < block)
; i = _heapinfo [i] . free.prev; 1
/* ����������, ��� �������� ���� ���� � ������ ���������. */
if (block == i + _heapinfo[i] . free. size) {
/* ����� ���� ���� � ��� ����������������. */ _heapinfo[i] .free. size
+= _heapinfo [block] .busy. info. size/block = i;
else
/* ������������� �������� ���� ���� � ������ ���������. */
_heapinf � [block] . free. size = _heapinfo [block] .busy. info. size;
_heapinf � [block] .free. next = _heapinfo[i] . free. next;
_heapinf � [block] . free.prev = i;
_heapinfo[i] .free. next = block;
_heapinf � [_heapinfo [block] .free. next] .free.prev = block;
++chunksfree;
/* ������, ��������� ���� �������, ���������, �� ����� �� ��
����� ��� � ��� �������������� (�������� ��� ������������� �� ������ �
��������� �������) . */
if (block + _heapinf � [block] . free. size == heapinfo [block] .free.
next)
{ _heapinfo [block] .free. size
+= _heapinfo [_heapinfo [block] .free. next] . free. size; _heapinfo [block]
.free. next
= _heapinfo[_heapinfo[block] .free. next] . free. next ; _heapinf � [_heapinfo[block]
.free. next] .free. prev = block; � chunksf ree ;
/* ���������, �� ����� �� �� ������� ������ �������. */
blocks = _heapinf � [block] .free. size;
if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
&& (*_morecore) (0) == ADDRESS (block + .blocks)) {
register size_t bytes = blocks * BLOCKSIZE; _heaplimit -= blocks;
(*__morecore) (-bytes); _heapinf � [_heapinf � [block] .free. prev] .free.
next
= _heapinf � [block] . free. next; _heapinfo[_heapinfo[block] .free. next]
.free. prev
= _heapinf � [block] . free. prev; block = _heapinf � [block] . free.
prev; � _chunks_f ree ; _bytes_free -= bytes;
/* ���������� ��������� �����, ���������� � ����� �����. */
_heapindex = block; break;
default:
/* ������� ��������� ����������. */
�_chunks_used; _bytes_used -= 1 � type; ++_chunks_free; bytes_free +=
1 � type;
/* �������� ����� ������� ���������� ��������� � ���� �����.
*/ prev = (struct list *) ((char *) ADDRESS (block) +
(_heapinfo[block].busy.info.frag.first � type));
#if 1 /* Adapted from Mike */
if (_heapinf�[block].busy.info.frag.nfree == (BLOCKSIZE � type) - 1
&& _fragblocks[type] > 1) #else
if (_heapinf�[block].busy.info.frag.nfree == (BLOCKSIZE � type) - 1)
#endif
lif 1 #endii
/* ���� ��� ��������� ����� ����� ��������, ������� �� �� ������ ����������
� ���������� ������ ����. */ /* Adapted from Mike */
� _f ragblocks [type] ;
next = prev;
for (i = 1; i < (size_t) (BLOCKSIZE � type)
next = next->next; prev->prev->next = next; if (next != NULL)
next->prev = prev->prev; _heapinf � [block] .busy. type = 0; _heapinf
� [block] .busy . info. size = 1;
/* ������ �� ��������� ����������.
*/ ++_chunks_used; _bytes_used += BLOCKSIZE; _chunks_free -= BLOCKSIZE
� type; _bytes_free -= BLOCKSIZE;
libc free (ADDRESS (block));
I
else if ( heapinf�[block].busy.info.frag.nfree != 0)
/* ���� ��������� ��������� ����� ����� ��������, ��������
���� �������� � ������ ���������� ����� ������� ���������� ��������� �����
�����. */
next = (struct list *) ptr;
next->next = prev->next;
next->prev = prev;
prev->next = next;
if (next->next != NULL) next->next->prev = next;
++_heapinf�[block].busy.info.frag.nfree;
else
/* � ���� ����� ��� ��������� ����������, ������� �������� ���� ��������
� ������ ���������� � ������������, ��� ��� ������ ��������� ��������
� ���� �����. */
prev = (struct list *) ptr;
_heapinfo [block] .busy. info. frag. nfree = 1;
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) ptr - (char *) NULL) % BLOCKSIZE � type)
; prev->next = _fraghead[type] .next; prev->prev = &_fraghead[type]
; prev->prev->next = prev; if (prev->next != NULL)
prev->next->prev = prev;
break;
/* ������� ������ � ����. */ void
_ libc_free (ptr) _ ptr_t ptr; {
register struct alignlist *1;
if (ptr == NULL) return;
for (1 = _aligned_blocks; 1 != NULL; 1 = l->next) if (l->aligned
== ptr)
{
l->aligned = NULL;
/* �������� ������� ������ ��� ���������. */
ptr = l->exact;
break;
if ( _ free_hook != NULL) (* _ free_hook) (ptr) ;
else
_free_internal (ptr) ;
#include <gnu-stabs . h>
#ifdef elf_alias
elf_alias (free, cfree) ;
#endif
� �������� ����������� ����� ��������� ��������� ������������� ������
������� ������ ����������� �����, ��� ������ ��� ������������ ��� �����
��������� �������. ��� ���� ����� ��������� ��������, ������� ��������
�� ������������� (����������, ���������) ����� ���� ����� ���������� ����
������, ���� ���� ������������ ����� � ���, ��� ����������� ����� �� ����������.
����� ����� ������ ��� ������, ���� ��� ��������� ����� ���������� �������������
�������� (���. 4.10). �� ���������� ����� ������� ������� � ���� ������.
���� � ������ ������ ���������� ������� ������ ���, �� ������� � ������
������ �������� �������. ���� ��� ���-�� ����, �� ��������� ���� ����
�� �����, ���� ������ ������������� ���������, � ������... ������, ����
������� ��������� ������ �� ������ ���� �����, ��� �� ����� ������ � ��������?
��� ������� ���� �������� ��� ���������� ������ �����-���� �����������
�� ������� ���������� ������. ��������, ����� �����������, ����� ��� �������
��������� ������ ��������� (������������������ ����� �����, � �������
Fi+1 = Fi + Fi-1. � ���� ������, ����
��� ����� Fi ����, � � ������� ���� ������ ���� ������� Fi+1,
�� ����� ����� �������� ��� ����� � ���� ���������� �������, � ������
� Fi-1, ������� ���� �� ��������. ��, ����� ����������� ��
������ �������� � ���������� ������������, �� ��� �� ������ ��� �����
�� ��������������� ����� ������ �����?

���. 4.10. ��������� ������ ������������� ��������
�� ��������, ����� ��������� �� ������������. ����� �� ������, ��-��������,
�������� ������������� ��������� ���������� ������ Fi, �������
�� ������ ���������� ������� �����. ������ ������� � ��������� �����������
��������� ������ �� �������� �������� � ���� �������� �������. ���� �������
���������� ����� ��������, ������� ������������ ���������������� �������
������ ����� ������� ������������ � ��������� ����� 2: 512 ����, 1 �����,
2 ����� � �. �. ����� ��������� ���������� ����������
��������� (���. 4.11).
���� �� ����������� ����� ������ ������� � �������� ����������� ������
��� �� ������������. ����� �����-�������� ���������� ������� ���������������
���������������� ���� � ������ ������ �����. ����� ������ ���������, ��������
�� ���� �������. ���� �� ��������, �� �� ���������� ������� � ���� �����
�������� �������, � �. �. ���� � ��������� ������ ����� ������ �� ���������
� (log(Smax)-log(Smin)), ��� Smax � Smin
����������, ��������������, ������������ � ����������� ������� ������������
������. ��� ������ �������� ��������� ������ ��������� ��� ��������, �
������� ���������� ��������������� ����� ������� � ��������, ���
����� ��������� �������. ����� ���� �������� ��� ��� �������� ������������
��� ��������� ������ ������ ���� ��.

���. 4.11. �������� ���������
���������� � ����� ������� �������� ���������� ���������� ���� �������.
��������, ��� ��������� ������ Novell Netware ������� �� 4 �������� �
����� 16 ���� (��� ������ ��������� 16, 32, 48, 64 �����), 3 ��������
� ����� 64 ����� (��� ������ ��������� 128, 192, 256 ����) � ����������
�������� � ����� 256 ���� (�� 512 ���� �� 4 �����). ��� �������� ��������
������� ���������� ������� ��������. ���������, ��� ����������� ������
� ������ ��������� �������, �������� ���� ���������� ���������, � Netware
����������� �� ������������.
��������, ���� ������� �������� ���������� ��� ��������� ���������� ������
������ ������������, ��� � ���� ��� ��������� ������� ��� ��� ������,
�� �� �������� �������� ����� ����� ����������� ����������. ������ �����,
������� ������ ���������� ��������� ������, ���� ���������� ������� ����������
�������. ��������� ��������� ������� ������ �� ���������� ����� ��������
� ������ ��� ���������� �� ���������� ������ �� ��������� �������� �������
�������� �������� ����� �����.
�������� ������ � ���������������� ������ ����� ���������� ��������, ��
���� ���������, ��� ��� �������� ������ �� ���� �������� � ������ �������
������ �������, �������� ����� ������ ��-�� ���������������� �����. �������
��� ������� ��������� �������� ������ ��������������� �������� ���������
������� � ������ �� ������, ������ �� ��������� ��� ������ �� ���� �������.
� ������ �������, � �������� ��������� ������� ������������� ������, �������
�� ��� ����� �� � ��������� ������� � ����������, � �������� ����� ������������,
���� � �� ������ ���������� ���������.
|