File: pl-segstack.c

package info (click to toggle)
swi-prolog 6.6.6-1~bpo70+1
  • links: PTS, VCS
  • area: main
  • in suites: wheezy-backports
  • size: 82,312 kB
  • sloc: ansic: 322,250; perl: 245,822; sh: 6,651; java: 5,254; makefile: 4,423; cpp: 4,153; ruby: 1,594; yacc: 843; xml: 82; sed: 12; sql: 6
file content (248 lines) | stat: -rw-r--r-- 7,039 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
/*  Part of SWI-Prolog

    Author:        Jan Wielemaker
    E-mail:        J.Wielemaker@vu.nl
    WWW:           http://www.swi-prolog.org
    Copyright (C): 1985-2013, University of Amsterdam
			      VU University Amsterdam

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
*/

/*#define O_DEBUG 1*/
#include "pl-incl.h"

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Segmented stack handling. A segmented stack is a stack that is allocated
in segments, This means we cannot   compare  addresses otherwise then by
identity.  We use a segmented stack for cycle detection.

Measurements with the chunksize on SuSE Linux  10.2 indicate there is no
measurable performance change above approximately  256 bytes. We'll keep
the figure on the safe  side  for   systems  with  less efficient malloc
implementations.

Note  that  atom-gc  requires   completely    asynchronous   calling  of
scanSegStack() and therefore pushSegStack()/popSegStack()  must push the
data before updating the pointers.

TBD: Avoid instruction/cache write reordering in push/pop.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

int
pushSegStack_(segstack *stack, void *data)
{ if ( stack->top + stack->unit_size <= stack->max )
  { memcpy(stack->top, data, stack->unit_size);
    stack->top += stack->unit_size;

    return TRUE;
  } else
  { segchunk *chunk = PL_malloc(SEGSTACK_CHUNKSIZE);

    if ( !chunk )
      return FALSE;			/* out of memory */

    chunk->allocated = TRUE;
    chunk->size = SEGSTACK_CHUNKSIZE;
    chunk->next = NULL;
    chunk->previous = stack->last;
    chunk->top = CHUNK_DATA(chunk);	/* async scanning */
    if ( stack->last )
    { stack->last->next = chunk;
      stack->last->top = stack->top;
      stack->top = chunk->top;		/* async scanning */
      stack->last = chunk;
    } else
    { stack->top = chunk->top;		/* async scanning */
      stack->last = stack->first = chunk;
    }

    stack->base = CHUNK_DATA(chunk);
    stack->max  = addPointer(chunk, chunk->size);
    memcpy(CHUNK_DATA(chunk), data, stack->unit_size);
    stack->top  = CHUNK_DATA(chunk) + stack->unit_size;

    return TRUE;
  }
}


int
pushRecordSegStack(segstack *stack, Record r)
{ if ( stack->top + sizeof(r) <= stack->max )
  { Record *rp = (Record*)stack->top;

    *rp++ = r;
    stack->top = (char*)rp;

    return TRUE;
  } else
  { return pushSegStack_(stack, &r);
  }
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Pop data. Note that we leave the first chunk associated with the stack
to speedup frequent small usage.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

int
popSegStack_(segstack *stack, void *data)
{ again:

  if ( stack->top >= stack->base + stack->unit_size )
  { stack->top -= stack->unit_size;
    memcpy(data, stack->top, stack->unit_size);

    return TRUE;
  } else
  { segchunk *chunk = stack->last;

    if ( chunk )
    { if ( chunk->previous )
      { stack->last = chunk->previous;
	stack->last->next = NULL;
	if ( chunk->allocated )
	  PL_free(chunk);

	chunk = stack->last;
	stack->base = CHUNK_DATA(chunk);
	stack->max  = addPointer(chunk, chunk->size);
	stack->top  = chunk->top;
	goto again;
      }
    }

    return FALSE;
  }
}


void *
topOfSegStack(segstack *stack)
{ segchunk *chunk;

  if ( stack->top >= stack->base + stack->unit_size )
  { return stack->top - stack->unit_size;
  } else if ( stack->last && (chunk=stack->last->previous) )
  { assert(chunk->top - stack->unit_size >= CHUNK_DATA(chunk));
    return chunk->top - stack->unit_size;
  }

  return NULL;
}


void
popTopOfSegStack_(segstack *stack)
{ again:

  if ( stack->top >= stack->base + stack->unit_size )
  { stack->top -= stack->unit_size;
  } else
  { segchunk *chunk = stack->last;

    if ( chunk )
    { if ( chunk->previous )
      { segchunk *del = chunk;

	stack->last = chunk->previous;
	stack->last->next = NULL;
	chunk = stack->last;
	stack->top  = chunk->top;
	MemoryBarrier();		/* Sync with scanSegStack() */
	stack->base = CHUNK_DATA(chunk);
	stack->max  = addPointer(chunk, chunk->size);

	if ( del->allocated )
	  PL_free(del);

	goto again;
      }
    }

    assert(0);
  }
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
scanSegStack(segstack *stack, void (*func)(void *cell))
Walk along all living cells on the stack and call func on them.  The stack
is traversed last-to-first.

This is used by markAtomsFindall(), which runs concurrent with findall/3
in the thread being scanned. New records pushed while AGC is in progress
are marked by findall/3 itself.  Findall/3   can  concurrently  pop this
stack. It may do this quicker than the   marking, but this is no problem
because the pointers remain valid as all   records  are reclaimed at the
end of findall/3 by calling clear_mem_pool(). It   is  only a problem if
popTopOfSegStack_() pops a chunk because  the   popped  chunk  is freed.
Therefore $collect_findall_bag/2 locks if it needs to call the expensive
chunk-popping popTopOfSegStack_().

With thanks to Eugeniy Meshcheryakov for   finding this and running many
tests. The issue is triggered by Tests/thread_agc_findall.pl, notably on
slow single core hardware.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

static inline void
scan_chunk(segstack *stack, char *top, char *base, void (*func)(void *cell))
{ while(top >= base+stack->unit_size)
  { top -= stack->unit_size;
    (*func)((void*)top);
  }
}


void
scanSegStack(segstack *stack, void (*func)(void *cell))
{ segchunk *chunk;

  if ( (chunk=stack->last) )		/* something there */
  { if ( stack->base == CHUNK_DATA(chunk) )
      chunk->top = stack->top;		/* close last chunk */
    for(; chunk; chunk=chunk->previous)
      scan_chunk(stack, chunk->top, CHUNK_DATA(chunk), func);
  }
}


void
clearSegStack_(segstack *s)
{ segchunk *c = s->first;
  segchunk *n;

  if ( !c->allocated )		/* statically allocated first chunk */
  { n = c->next;

    c->next = NULL;
    s->last = c;
    s->base = s->top = c->top;
    s->max  = addPointer(c, c->size);

    for(c=n; c; c = n)
    { n = c->next;
      PL_free(c);
    }
  } else				/* all dynamic chunks */
  { for(; c; c = n)
    { n = c->next;
      PL_free(c);
    }
    memset(s, 0, sizeof(*s));
  }
}