csh and tcsh work

Sources of csh/alloc.c

csh と tcsh のソース

Bill Joy

First published: October, 1978.

Copyright © 1979 Regents of the University of California.

  1. 1
    /* Copyright (c) 1979 Regents of the University of California */
  2. 2
    #include "sh.local.h"
  3. 3
    #ifdef debug
  4. 4
    #define ASSERT(p) if(!(p))botch("p");else
  5. 5
    botch(s)
  6. 6
    char *s;
  7. 7
    {
  8. 8
    	printf("assertion botched: %s\n",s);
  9. 9
    	abort();
  10. 10
    }
  11. 11
    #else
  12. 12
    #define ASSERT(p)
  13. 13
    #endif
  14. 14
  15. 15
    /*	avoid break bug */
  16. 16
    #ifdef pdp11
  17. 17
    #define GRANULE 64
  18. 18
    #else
  19. 19
    #define GRANULE 0
  20. 20
    #endif
  21. 21
    /*	C storage allocator
  22. 22
     *	circular first-fit strategy
  23. 23
     *	works with noncontiguous, but monotonically linked, arena
  24. 24
     *	each block is preceded by a ptr to the (pointer of)
  25. 25
     *	the next following block
  26. 26
     *	blocks are exact number of words long
  27. 27
     *	aligned to the data type requirements of ALIGN
  28. 28
     *	pointers to blocks must have BUSY bit 0
  29. 29
     *	bit in ptr is 1 for busy, 0 for idle
  30. 30
     *	gaps in arena are merely noted as busy blocks
  31. 31
     *	last block of arena (pointed to by alloct) is empty and
  32. 32
     *	has a pointer to first
  33. 33
     *	idle blocks are coalesced during space search
  34. 34
     *
  35. 35
     *	a different implementation may need to redefine
  36. 36
     *	ALIGN, NALIGN, BLOCK, BUSY, INT
  37. 37
     *	where INT is integer type to which a pointer can be cast
  38. 38
    */
  39. 39
    #define INT int
  40. 40
    #define ALIGN int
  41. 41
    #define NALIGN 1
  42. 42
    #define WORD sizeof(union store)
  43. 43
    #define BLOCK 1024	/* a multiple of WORD*/
  44. 44
    #define BUSY 1
  45. 45
    #define NULL 0
  46. 46
    #define testbusy(p) ((INT)(p)&BUSY)
  47. 47
    #define setbusy(p) (union store *)((INT)(p)|BUSY)
  48. 48
    #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  49. 49
  50. 50
    union store { union store *ptr;
  51. 51
    	      ALIGN dummy[NALIGN];
  52. 52
    	      int calloc;	/*calloc clears an array of integers*/
  53. 53
    };
  54. 54
  55. 55
    static	union store allocs[2];	/*initial arena*/
  56. 56
    static	union store *allocp;	/*search ptr*/
  57. 57
    static	union store *alloct;	/*arena top*/
  58. 58
    static	union store *allocx;	/*for benefit of realloc*/
  59. 59
    char	*sbrk();
  60. 60
  61. 61
    char *
  62. 62
    malloc(nbytes)
  63. 63
    unsigned nbytes;
  64. 64
    {
  65. 65
    	register union store *p, *q;
  66. 66
    	register nw;
  67. 67
    	static temp;	/*coroutines assume no auto*/
  68. 68
  69. 69
    	if(allocs[0].ptr==0) {	/*first time*/
  70. 70
    		allocs[0].ptr = setbusy(&allocs[1]);
  71. 71
    		allocs[1].ptr = setbusy(&allocs[0]);
  72. 72
    		alloct = &allocs[1];
  73. 73
    		allocp = &allocs[0];
  74. 74
    	}
  75. 75
    	nw = (nbytes+WORD+WORD-1)/WORD;
  76. 76
    	ASSERT(allocp>=allocs && allocp<=alloct);
  77. 77
    	ASSERT(allock());
  78. 78
    	for(p=allocp; ; ) {
  79. 79
    		for(temp=0; ; ) {
  80. 80
    			if(!testbusy(p->ptr)) {
  81. 81
    				while(!testbusy((q=p->ptr)->ptr)) {
  82. 82
    					ASSERT(q>p&&q<alloct);
  83. 83
    					p->ptr = q->ptr;
  84. 84
    				}
  85. 85
    				if(q>=p+nw && p+nw>=p)
  86. 86
    					goto found;
  87. 87
    			}
  88. 88
    			q = p;
  89. 89
    			p = clearbusy(p->ptr);
  90. 90
    			if(p>q)
  91. 91
    				ASSERT(p<=alloct);
  92. 92
    			else if(q!=alloct || p!=allocs) {
  93. 93
    				ASSERT(q==alloct&&p==allocs);
  94. 94
    				return(NULL);
  95. 95
    			} else if(++temp>1)
  96. 96
    				break;
  97. 97
    		}
  98. 98
    		temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
  99. 99
    		q = (union store *)sbrk(0);
  100. 100
    		if(q+temp+GRANULE < q) {
  101. 101
    			return(NULL);
  102. 102
    		}
  103. 103
    		q = (union store *)sbrk(temp*WORD);
  104. 104
    		if((INT)q == -1) {
  105. 105
    			return(NULL);
  106. 106
    		}
  107. 107
    		ASSERT(q>alloct);
  108. 108
    		alloct->ptr = q;
  109. 109
    		if(q!=alloct+1)
  110. 110
    			alloct->ptr = setbusy(alloct->ptr);
  111. 111
    		alloct = q->ptr = q+temp-1;
  112. 112
    		alloct->ptr = setbusy(allocs);
  113. 113
    	}
  114. 114
    found:
  115. 115
    	allocp = p + nw;
  116. 116
    	ASSERT(allocp<=alloct);
  117. 117
    	if(q>allocp) {
  118. 118
    		allocx = allocp->ptr;
  119. 119
    		allocp->ptr = p->ptr;
  120. 120
    	}
  121. 121
    	p->ptr = setbusy(allocp);
  122. 122
    	return((char *)(p+1));
  123. 123
    }
  124. 124
  125. 125
    /*	freeing strategy tuned for LIFO allocation
  126. 126
    */
  127. 127
    free(ap)
  128. 128
    register char *ap;
  129. 129
    {
  130. 130
    	register union store *p = (union store *)ap;
  131. 131
  132. 132
    	ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
  133. 133
    	ASSERT(allock());
  134. 134
    	allocp = --p;
  135. 135
    /* 	ASSERT(testbusy(p->ptr)); */
  136. 136
    	p->ptr = clearbusy(p->ptr);
  137. 137
    	ASSERT(p->ptr > allocp && p->ptr <= alloct);
  138. 138
    }
  139. 139
  140. 140
    /*	realloc(p, nbytes) reallocates a block obtained from malloc()
  141. 141
     *	and freed since last call of malloc()
  142. 142
     *	to have new size nbytes, and old content
  143. 143
     *	returns new location, or 0 on failure
  144. 144
    */
  145. 145
  146. 146
    char *
  147. 147
    realloc(p, nbytes)
  148. 148
    register union store *p;
  149. 149
    unsigned nbytes;
  150. 150
    {
  151. 151
    	register union store *q;
  152. 152
    	union store *s, *t;
  153. 153
    	register unsigned nw;
  154. 154
    	unsigned onw;
  155. 155
  156. 156
    	if(testbusy(p[-1].ptr))
  157. 157
    		free((char *)p);
  158. 158
    	onw = p[-1].ptr - p;
  159. 159
    	q = (union store *)malloc(nbytes);
  160. 160
    	if(q==NULL || q==p)
  161. 161
    		return((char *)q);
  162. 162
    	s = p;
  163. 163
    	t = q;
  164. 164
    	nw = (nbytes+WORD-1)/WORD;
  165. 165
    	if(nw<onw)
  166. 166
    		onw = nw;
  167. 167
    	while(onw--!=0)
  168. 168
    #ifdef	V6
  169. 169
    		copy(t++, s++, sizeof (*t));
  170. 170
    #else
  171. 171
    		*t++ = *s++;
  172. 172
    #endif
  173. 173
    	if(q<p && q+nw>=p)
  174. 174
    		(q+(q+nw-p))->ptr = allocx;
  175. 175
    	return((char *)q);
  176. 176
    }
  177. 177
  178. 178
    #ifdef debug
  179. 179
    allock()
  180. 180
    {
  181. 181
    #ifdef longdebug
  182. 182
    	register union store *p;
  183. 183
    	int x;
  184. 184
    	x = 0;
  185. 185
    	for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
  186. 186
    		if(p==allocp)
  187. 187
    			x++;
  188. 188
    	}
  189. 189
    	ASSERT(p==alloct);
  190. 190
    	return(x==1|p==allocp);
  191. 191
    #else
  192. 192
    	return(1);
  193. 193
    #endif
  194. 194
    }
  195. 195
    #endif
  196. 196
  197. 197
    #ifdef debug
  198. 198
    showall(v)
  199. 199
    	char **v;
  200. 200
    {
  201. 201
    	register union store *p, *q;
  202. 202
    	int used = 0, free = 0, i;
  203. 203
  204. 204
    	for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
  205. 205
    		q = clearbusy(p->ptr);
  206. 206
    		if (v[1])
  207. 207
    		printf("%6o %5d %s\n", p,
  208. 208
    		    ((unsigned) q - (unsigned) p),
  209. 209
    		    testbusy(p->ptr) ? "BUSY" : "FREE");
  210. 210
    		i = ((unsigned) q - (unsigned) p);
  211. 211
    		if (testbusy(p->ptr)) used += i; else free += i;
  212. 212
    	}
  213. 213
    	printf("%d used, %d free, %l end\n", used, free, clearbusy(alloct));
  214. 214
    }
  215. 215
    #endif

To the top of this page