1 #if !defined(INCLUDED_GSFIFO)
2 #define INCLUDED_GSFIFO 1
3 /**
4 Copyright (C) 2011 Free Software Foundation, Inc.
5
6 Written by: Richard Frith-Macdonald <rfm@gnu.org>
7 Date: April 2011
8
9 This file is part of the Performance Library.
10
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU Lesser General Public
13 License as published by the Free Software Foundation; either
14 version 3 of the License, or (at your option) any later version.
15
16 This library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 Lesser General Public License for more details.
20
21 You should have received a copy of the GNU Lesser General Public
22 License along with this library; if not, write to the Free
23 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA.
24 */
25 #import <Foundation/NSObject.h>
26
27 @class NSArray;
28 @class NSCondition;
29 @class NSNumber;
30 @class NSString;
31 @class NSThread;
32
33
34 /** GSFIFO manages a first-in-first-out queue of items.<br />
35 * Items in the queue are <em>NOT</em> retained objects ... memory management
36 * is not the job of this class and it is not intended to be treated
37 * as a 'collection', rather its role is intended to be that of an
38 * inter-thread coordination mechanism.<br />
39 * Instances of the GSFIFO class are intended to support the producer-consumer
40 * model of processing. The ideal example is that of a production line,
41 * where you have a stream of items to be processed and while that processing
42 * can be broken down into separate stages, they must be done in a particular
43 * order. The FIFO is used as the link betwen those stages, ensuring that
44 * the required ordering is maintained even when separate threads handle
45 * each stage.<br />
46 * Where there is a single producer and a single consumer thread, a fast
47 * lock-free algorthm is used to get/pu items from the FIFO.<br />
48 * To minimise the overheads of using the FIFO, we provide inline functions
49 * to support the addition of items in the single producer thread case and to
50 * support the removal of items in the single consumer thread case. When
51 * operating that way, the overhead of using the FIFO is only a few CPU cycles
52 * and it becomes reasonable to split sequentional processing into a long
53 * series of small operations each handled by a separate thread (making
54 * effective use of a multi-cpu machine).<br />
55 * The FIFO may also be useful where you don't have a strictly sequential
56 * process to manage, but some parts need to be sequential ... in these
57 * cases it may make sense to have multiple consumers and/or producers.
58 * In these cases, some locking is required and the use of the inline
59 * functions is not allowed (you must call the -get and -put: methods.<br />
60 * It is recommended that you create FIFOs using the -initWithName: method
61 * so that you can easily use the NSUserDefaults system to adjust their
62 * configurations to tests/tweak performance.
63 */
64 @interface GSFIFO : NSObject
65 {
66 @public
67 /* While the following instance variables are nominally public, they are in
68 * fact only intended to be used by the provided inline functions ... you
69 * should not access them directly in your own code.
70 */
71 volatile uint64_t _head;
72 volatile uint64_t _tail;
73 uint64_t _getTryFailure;
74 uint64_t _getTrySuccess;
75 uint64_t _putTryFailure;
76 uint64_t _putTrySuccess;
77 void **_items;
78 uint32_t _capacity;
79 @private
80 uint32_t boundsCount;
81 uint16_t granularity;
82 uint16_t timeout;
83 uint64_t fullCount; // Total waits for full FIFO
84 uint64_t emptyCount; // Total waits for empty FIFO
85 NSCondition *condition;
86 NSString *name;
87 NSTimeInterval getWaitTotal; // Total time waiting for gets
88 NSTimeInterval putWaitTotal; // Total time waiting for puts
89 NSTimeInterval *waitBoundaries; // Stats boundaries
90 uint64_t *getWaitCounts; // Waits for gets by time
91 uint64_t *putWaitCounts; // Waits for puts by time
92 NSThread *getThread; // Single consumer thread
93 NSThread *putThread; // Single producer thread
94 }
95
96 /** Return statistics for all current GSFIFO instances.<br />
97 * Statistics for FIFOs which are configued to be lock-free are empty
98 * (listing the name only) except where we can safely obtain get or put
99 * stats because the FIFOs consumer/producer thread is the same as the
100 * current thread.
101 */
102 + (NSString*) stats;
103
104 /** Returns the approximate number of items in the FIFO.
105 */
106 - (NSUInteger) count;
107
108 /** Reads up to count items from the FIFO into buf.
109 * If block is YES, this blocks if necessary until at least one item
110 * is available, and raises an exception if the FIFO is configured
111 * with a timeout and it is exceeded.<br />
112 * Returns the number of items actually read.
113 */
114 - (unsigned) get: (void**)buf count: (unsigned)count shouldBlock: (BOOL)block;
115
116 /** Gets the next item from the FIFO, blocking if necessary until an
117 * item is available. Raises an exception if the FIFO is configured
118 * with a timeout and it is exceeded.<br />
119 * Implemented using -get:count:shouldBlock:
120 */
121 - (void*) get;
122
123 /** <init/>
124 * Initialises the receiver with the specified capacity (buffer size).<br />
125 * The capacity must lie in the range from one to a million, othewrwise
126 * the receiver is deallocated and this method returns nil.<br />
127 * If the granularity value is non-zero, it is treated as the maximum time
128 * in milliseconds for which a -get or -put: operation will pause between
129 * successive attempts.<br />
130 * If the timeout value is non-zero, it is treated as the total time in
131 * milliseconds for which a -get or -put: operation may block, and a
132 * longer delay will cause those methods to raise an exception.<br />
133 * If the multiProducer or multiConsumer flag is YES, the FIFO is
134 * configured to support multiple producer/consumer threads using locking.<br />
135 * The boundaries array is an ordered list of NSNumber objects containing
136 * time intervals found boundaries of bands into which to categorise wait
137 * time stats. Any wait whose duration is less than the interval specified
138 * in the Nth element is counted in the stat's for the Nth band.
139 * If this is nil, a default set of bundaries is used. If it is an empty
140 * array then no time based stats are recorded.<br />
141 * The name string is a unique identifier for the receiver and is used when
142 * printing diagnostics and statistics. If an instance with the same name
143 * already exists, the receiveris deallocated and an exception is raised.
144 */
145 - (id) initWithCapacity: (uint32_t)c
146 granularity: (uint16_t)g
147 timeout: (uint16_t)t
148 multiProducer: (BOOL)mp
149 multiConsumer: (BOOL)mc
150 boundaries: (NSArray*)a
151 name: (NSString*)n;
152
153 /** Initialises the receiver as a multi-producer, multi-consumer FIFO with
154 * no timeout and with default stats gathering enabled.<br />
155 * However, these values (including the supplied capacity) may be overridden
156 * as specified in -initWithName:
157 */
158 - (id) initWithCapacity: (uint32_t)c
159 name: (NSString*)n;
160
161 /** Initialises the receiver using the specified name and obtaining other
162 * details from the NSUserDefaults system using defaults keys where 'NNN'
163 * is the supplied name.<br />
164 * The GSFIFOCapacityNNN default specifies the capacity for the FIFO, and
165 * if missing a capacity of 1000 is assumed.<br />
166 * The GSFIFOGranularityNNN integer is zero by default.<br />
167 * The GSFIFOTimeoutNNN integer is zero by default.<br />
168 * The GSFIFOSingleConsumerNNN boolean is NO by default.<br />
169 * The GSFIFOSingleProducerNNN boolean is NO by default.<br />
170 * The GSFIFOBoundariesNNN array is missing by default.<br />
171 */
172 - (id) initWithName: (NSString*)n;
173
174 /** Writes up to count items from buf into the FIFO.
175 * If block is YES, this blocks if necessary until at least one item
176 * can be written, and raises an exception if the FIFO is configured
177 * with a timeout and it is exceeded.<br />
178 * Returns the number of items actually written.
179 */
180 - (unsigned) put: (void**)buf count: (unsigned)count shouldBlock: (BOOL)block;
181
182 /** Adds an item to the FIFO, blocking if necessary until there is
183 * space in the buffer. Raises an exception if the FIFO is configured
184 * with a timeout and it is exceeded.br />
185 * Implemented using -put:count:shouldBlock:
186 */
187 - (void) put: (void*)item;
188
189 /** Return any available statistics for the receiver.<br />
190 */
191 - (NSString*) stats;
192
193 /** Return statistics on get operations for the receiver.<br />
194 * NB. If the recever is not configured for multiple consumers,
195 * this method may only be called from the single consumer thread.
196 */
197 - (NSString*) statsGet;
198
199 /** Return statistics on put operations for the receiver.<br />
200 * NB. If the recever is not configured for multiple producers,
201 * this method may only be called from the single producer thread.
202 */
203 - (NSString*) statsPut;
204
205 /** Checks the FIFO and returns the first available item or NULL if the
206 * FIFO is empty.<br />
207 * Implemented using -get:count:shouldBlock:
208 */
209 - (void*) tryGet;
210
211 /** Attempts to put an item into the FIFO, returning YES on success or NO
212 * if the FIFO is full.<br />
213 * Implemented using -put:count:shouldBlock:
214 */
215 - (BOOL) tryPut: (void*)item;
216 @end
217
218 /** Function to efficiently get an item from a fast FIFO.<br />
219 * Returns NULL if the FIFO is empty.<br />
220 * Warning ... only for use if the FIFO is NOT configured for multiple
221 * consumers.
222 */
223 static inline void*
GSGetFastNonBlockingFIFO(GSFIFO * receiver)224 GSGetFastNonBlockingFIFO(GSFIFO *receiver)
225 {
226 if (receiver->_head > receiver->_tail)
227 {
228 void *item;
229
230 item = receiver->_items[receiver->_tail % receiver->_capacity];
231 receiver->_tail++;
232 receiver->_getTrySuccess++;
233 return item;
234 }
235 receiver->_getTryFailure++;
236 return NULL;
237 }
238
239 /** Function to efficiently get an item from a fast FIFO, blocking if
240 * necessary until an item is available or the timeout occurs.<br />
241 * Warning ... only for use if the FIFO is NOT configured for multiple
242 * consumers.
243 */
244 static inline void*
GSGetFastFIFO(GSFIFO * receiver)245 GSGetFastFIFO(GSFIFO *receiver)
246 {
247 void *item = GSGetFastNonBlockingFIFO(receiver);
248
249 if (0 == item)
250 {
251 item = [receiver get];
252 }
253 return item;
254 }
255
256 /** Function to efficiently put an item to a fast FIFO.<br />
257 * Returns YES on success, NO on failure (FIFO is full).<br />
258 * Warning ... only for use if the FIFO is NOT configured for multiple
259 * producers.
260 */
261 static inline BOOL
GSPutFastNonBlockingFIFO(GSFIFO * receiver,void * item)262 GSPutFastNonBlockingFIFO(GSFIFO *receiver, void *item)
263 {
264 if (receiver->_head - receiver->_tail < receiver->_capacity)
265 {
266 receiver->_items[receiver->_head % receiver->_capacity] = item;
267 receiver->_head++;
268 receiver->_putTrySuccess++;
269 return YES;
270 }
271 receiver->_putTryFailure++;
272 return NO;
273 }
274
275 /** Function to efficiently put an item to a fast FIFO, blocking if
276 * necessary until there is space in the FIFO or until the timeout
277 * occurs.<br />
278 * Warning ... only for use if the FIFO is NOT configured for multiple
279 * producers.
280 */
281 static inline void
GSPutFastFIFO(GSFIFO * receiver,void * item)282 GSPutFastFIFO(GSFIFO *receiver, void *item)
283 {
284 if (NO == GSPutFastNonBlockingFIFO(receiver, item))
285 {
286 [receiver put: item];
287 }
288 }
289
290 #endif
291