1 /*
2 * Cache.hpp
3 *
4 * Created on: Feb 24, 2009
5 * Author: benoit tbolsee
6 */
7
8 #ifndef CACHE_HPP_
9 #define CACHE_HPP_
10
11 #include <map>
12
13 namespace iTaSC {
14
15 #define CACHE_LOOKUP_TABLE_SIZE 128
16 #define CACHE_DEFAULT_BUFFER_SIZE 32768
17 #define CACHE_CHANNEL_EXTEND_SIZE 10
18 #define CACHE_MAX_ITEM_SIZE 0x3FFF0
19
20 /* macro to get the alignement gap after an item header */
21 #define CACHE_ITEM_GAPB(item) (unsigned int)(((size_t)item+sizeof(CacheItem))&(sizeof(void*)-1))
22 /* macro to get item data position, item=CacheItem pointer */
23 #define CACHE_ITEM_DATA_POINTER(item) (void*)((unsigned char*)item+sizeof(CacheItem)+CACHE_ITEM_GAPB(item))
24 /* macro to get item size in 32bit words from item address and length, item=CacheItem pointer */
25 #define CACHE_ITEM_SIZEW(item,length) (unsigned int)((sizeof(CacheItem)+CACHE_ITEM_GAPB(item)+(((length)+3)&~0x3))>>2)
26 /* macto to move from one item to the next, item=CacheItem pointer, updated by the macro */
27 #define CACHE_NEXT_ITEM(item) ((item)+(item)->m_sizeW)
28 #define CACHE_BLOCK_ITEM_ADDR(chan,buf,block) (&(buf)->m_firstItem+(((unsigned int)(block)<<chan->m_positionToBlockShiftW)+(buf)->lookup[block].m_offsetW))
29 #define CACHE_ITEM_ADDR(buf,pos) (&(buf)->m_firstItem+(pos))
30 #define CACHE_ITEM_POSITIONW(buf,item) (unsigned int)(item-&buf->m_firstItem)
31
32 typedef unsigned int CacheTS;
33
34 struct Timestamp
35 {
36 double realTimestamp;
37 double realTimestep;
38 CacheTS cacheTimestamp;
39 unsigned int numstep:8;
40 unsigned int substep:1;
41 unsigned int reiterate:1;
42 unsigned int cache:1;
43 unsigned int update:1;
44 unsigned int interpolate:1;
45 unsigned int dummy:19;
46
TimestampiTaSC::Timestamp47 Timestamp() { memset(this, 0, sizeof(Timestamp)); }
48 };
49
50 /* utility function to return second timestamp to millisecond */
setCacheTimestamp(Timestamp & timestamp)51 inline void setCacheTimestamp(Timestamp& timestamp)
52 {
53 if (timestamp.realTimestamp < 0.0 || timestamp.realTimestamp > 4294967.295)
54 timestamp.cacheTimestamp = 0;
55 else
56 timestamp.cacheTimestamp = (CacheTS)(timestamp.realTimestamp*1000.0+0.5);
57 }
58
59
60 /*
61 class Cache:
62 Top level class, only one instance of this class should exists.
63 A device (=constraint, object) uses this class to create a cache entry for its data.
64 A cache entry is divided into cache channels, each providing a separate buffer for cache items.
65 The cache channels must be declared by the devices before they can be used.
66 The device must specify the largest cache item (limited to 256Kb) so that the cache
67 buffer can be organized optimally.
68 Cache channels are identified by small number (starting from 0) allocated by the cache system.
69 Cache items are inserted into cache channels ordered by timestamp. Writing is always done
70 at the end of the cache buffer: writing an item automatically clears all items with
71 higher timestamp.
72 A cache item is an array of bytes provided by the device; the format of the cache item is left
73 to the device.
74 The device can retrieve a cache item associated with a certain timestamp. The cache system
75 returns a pointer that points directly in the cache buffer to avoid unnecessary copy.
76 The pointer is guaranteed to be pointer aligned so that direct mapping to C structure is possible
77 (=32 bit aligned on 32 systems and 64 bit aligned on 64 bits system).
78
79 Timestamp = rounded time in millisecond.
80 */
81
82 struct CacheEntry;
83 struct CacheBuffer;
84 struct CacheItem;
85 struct CacheChannel;
86
87 class Cache
88 {
89 private:
90 /* map between device and cache entry.
91 Dynamically updated when more devices create cache channels */
92 typedef std::map<const void *, struct CacheEntry*> CacheMap;
93 CacheMap m_cache;
94 const CacheItem *getCurrentCacheItemInternal(const void *device, int channel, CacheTS timestamp);
95
96 public:
97 Cache();
98 ~Cache();
99 /* add a cache channel, maxItemSize must be < 256k.
100 name : channel name, truncated at 31 characters
101 msxItemSize : maximum size of item in bytes, items of larger size will be rejected
102 return value >= 0: channel id, -1: error */
103 int addChannel(const void *device, const char *name, unsigned int maxItemSize);
104
105 /* delete a cache channel (and all associated buffers and items) */
106 int deleteChannel(const void *device, int channel);
107 /* delete all channels of a device and remove the device from the map */
108 int deleteDevice(const void *device);
109 /* removes all cache items, leaving the special item at timestamp=0.
110 if device=NULL, apply to all devices. */
111 void clearCacheFrom(const void *device, CacheTS timestamp);
112
113 /* add a new cache item
114 channel: the cache channel (as returned by AddChannel
115 data, length: the cache item and length in bytes
116 If data is NULL, the memory is allocated in the cache but not writen
117 return: error: NULL, success: pointer to item in cache */
118 void *addCacheItem(const void *device, int channel, CacheTS timestamp, void *data, unsigned int length);
119
120 /* specialized function to add a vector of double in the cache
121 It will first check if a vector exist already in the cache for the same timestamp
122 and compared the cached vector with the new values.
123 If all values are within threshold, the vector is updated but the cache is not deleted
124 for the future timestamps. */
125 double *addCacheVectorIfDifferent(const void *device, int channel, CacheTS timestamp, double *data, unsigned int length, double threshold);
126
127 /* returns the cache item with timestamp that is just before the given timestamp.
128 returns the data pointer or NULL if there is no cache item before timestamp.
129 On return, timestamp is updated with the actual timestamp of the item being returned.
130 Note that the length of the item is not returned, it is up to the device to organize
131 the data so that length can be retrieved from the data if needed.
132 Device can NULL, it will then just look the first channel available, useful to
133 test the status of the cache. */
134 const void *getPreviousCacheItem(const void *device, int channel, CacheTS *timestamp);
135
136 /* returns the cache item with the timestamp that is exactly equal to the given timestamp
137 If there is no cache item for this timestamp, returns NULL.*/
138 const void *getCurrentCacheItem(const void *device, int channel, CacheTS timestamp);
139
140 };
141
142 /* the following structures are not internal use only, they should not be used directly */
143
144 struct CacheEntry
145 {
146 CacheChannel *m_channelArray; // array of channels, automatically resized if more channels are created
147 unsigned int m_count; // number of channel in channelArray
CacheEntryiTaSC::CacheEntry148 CacheEntry() : m_channelArray(NULL), m_count(0) {}
149 ~CacheEntry();
150 };
151
152 struct CacheChannel
153 {
154 CacheItem* initItem; // item corresponding to timestamp=0
155 struct CacheBuffer *m_firstBuffer; // first buffer of list
156 struct CacheBuffer *m_lastBuffer; // last buffer of list to which an item was written
157 char m_name[32]; // channel name
158 unsigned char m_busy; // =0 if channel is free, !=0 when channel is in use
159 unsigned char m_positionToBlockShiftW; // number of bits to shift a position in word to get the block number
160 unsigned short m_positionToOffsetMaskW; // bit mask to apply on a position in word to get offset in a block
161 unsigned int m_maxItemSizeB; // maximum item size in bytes
162 unsigned int m_bufferSizeW; // size of item buffer in word to allocate when a new buffer must be created
163 unsigned int m_blockSizeW; // block size in words of the lookup table
164 unsigned int m_lastTimestamp; // timestamp of the last item that was written
165 unsigned int m_lastItemPositionW; // position in words in lastBuffer of the last item written
166 void clear();
167 CacheBuffer* allocBuffer();
168 CacheItem* findItemOrLater(unsigned int timestamp, CacheBuffer **rBuffer);
169 CacheItem* findItemEarlier(unsigned int timestamp, CacheBuffer **rBuffer);
170 // Internal function: finds an item in a buffer that is < timeOffset
171 // timeOffset must be a valid offset for the buffer and the buffer must not be empty
172 // on return highBlock contains the block with items above or equal to timeOffset
173 CacheItem *_findBlock(CacheBuffer *buffer, unsigned short timeOffset, unsigned int *highBlock);
174 };
175
176 struct CacheBlock {
177 unsigned short m_timeOffset; // timestamp relative to m_firstTimestamp
178 unsigned short m_offsetW; // position in words of item relative to start of block
179 };
180
181 /* CacheItem is the header of each item in the buffer, must be 32bit
182 Items are always 32 bits aligned and size is the number of 32 bit words until the
183 next item header, including an eventual pre and post padding gap for pointer alignment */
184 struct CacheItem
185 {
186 unsigned short m_timeOffset; // timestamp relative to m_firstTimestamp
187 unsigned short m_sizeW; // size of item in 32 bit words
188 // item data follows header immediately or after a gap if position is not pointer aligned
189 };
190
191 // Buffer header
192 // Defined in a macro to avoid sizeof() potential problem.
193 // next for linked list. = NULL for last buffer
194 // m_firstTimestamp timestamp of first item in this buffer
195 // m_lastTimestamp timestamp of last item in this buffer
196 // m_lastTimestamp must be < m_firstTimestamp+65536
197 // m_lastItemPositionW position in word of last item written
198 // m_firstFreePositionW position in word where a new item can be written, 0 if buffer is empty
199 // lookup lookup table for fast access to item by timestamp
200 // The buffer is divided in blocks of 2**n bytes with n chosen so that
201 // there are no more than CACHE_LOOKUP_TABLE_SIZE blocks and that each
202 // block will contain at least one item.
203 // Each element of the lookup table gives the timestamp and offset
204 // of the last cache item occupying (=starting in) the corresponding block.
205 #define CACHE_HEADER \
206 struct CacheBuffer *m_next; \
207 unsigned int m_firstTimestamp; \
208 unsigned int m_lastTimestamp; \
209 \
210 unsigned int m_lastItemPositionW; \
211 unsigned int m_firstFreePositionW;\
212 struct CacheBlock lookup[CACHE_LOOKUP_TABLE_SIZE]
213
214 struct CacheBufferHeader {
215 CACHE_HEADER;
216 };
217 #define CACHE_BUFFER_HEADER_SIZE (sizeof(struct CacheBufferHeader))
218 struct CacheBuffer
219 {
220 CACHE_HEADER;
221 struct CacheItem m_firstItem; // the address of this field marks the start of the buffer
222 };
223
224
225 }
226
227 #endif /* CACHE_HPP_ */
228