Blender  V3.3
Cache.hpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: LGPL-2.1-or-later
2  * Copyright 2009 Benoit Bolsee. */
3 
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 alignment 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;
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 
47  Timestamp() { memset(this, 0, sizeof(Timestamp)); }
48 };
49 
50 /* utility function to return second timestamp to millisecond */
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
149  ~CacheEntry();
150 };
151 
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();
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 
216 };
217 #define CACHE_BUFFER_HEADER_SIZE (sizeof(struct CacheBufferHeader))
219 {
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_ */
const void * getCurrentCacheItem(const void *device, int channel, CacheTS timestamp)
Definition: Cache.cpp:593
void clearCacheFrom(const void *device, CacheTS timestamp)
Definition: Cache.cpp:321
int deleteChannel(const void *device, int channel)
Definition: Cache.cpp:289
int addChannel(const void *device, const char *name, unsigned int maxItemSize)
Definition: Cache.cpp:201
int deleteDevice(const void *device)
Definition: Cache.cpp:306
void * addCacheItem(const void *device, int channel, CacheTS timestamp, void *data, unsigned int length)
Definition: Cache.cpp:403
double * addCacheVectorIfDifferent(const void *device, int channel, CacheTS timestamp, double *data, unsigned int length, double threshold)
Definition: Cache.cpp:599
const void * getPreviousCacheItem(const void *device, int channel, CacheTS *timestamp)
Definition: Cache.cpp:543
ccl_global float * buffer
ccl_gpu_kernel_postfix ccl_global float int int int int float threshold
T length(const vec_base< T, Size > &a)
void setCacheTimestamp(Timestamp &timestamp)
Definition: Cache.hpp:51
unsigned int CacheTS
Definition: Cache.hpp:32
unsigned short m_offsetW
Definition: Cache.hpp:178
unsigned short m_timeOffset
Definition: Cache.hpp:177
struct CacheItem m_firstItem
Definition: Cache.hpp:221
CacheItem * _findBlock(CacheBuffer *buffer, unsigned short timeOffset, unsigned int *highBlock)
Definition: Cache.cpp:24
struct CacheBuffer * m_firstBuffer
Definition: Cache.hpp:155
unsigned int m_maxItemSizeB
Definition: Cache.hpp:161
unsigned int m_blockSizeW
Definition: Cache.hpp:163
CacheItem * initItem
Definition: Cache.hpp:154
struct CacheBuffer * m_lastBuffer
Definition: Cache.hpp:156
char m_name[32]
Definition: Cache.hpp:157
CacheBuffer * allocBuffer()
Definition: Cache.cpp:87
unsigned char m_positionToBlockShiftW
Definition: Cache.hpp:159
unsigned int m_lastItemPositionW
Definition: Cache.hpp:165
unsigned int m_bufferSizeW
Definition: Cache.hpp:162
unsigned char m_busy
Definition: Cache.hpp:158
CacheItem * findItemEarlier(unsigned int timestamp, CacheBuffer **rBuffer)
Definition: Cache.cpp:136
unsigned short m_positionToOffsetMaskW
Definition: Cache.hpp:160
CacheItem * findItemOrLater(unsigned int timestamp, CacheBuffer **rBuffer)
Definition: Cache.cpp:99
unsigned int m_lastTimestamp
Definition: Cache.hpp:164
unsigned int m_count
Definition: Cache.hpp:147
CacheChannel * m_channelArray
Definition: Cache.hpp:146
unsigned short m_timeOffset
Definition: Cache.hpp:186
unsigned short m_sizeW
Definition: Cache.hpp:187
unsigned int interpolate
Definition: Cache.hpp:44
double realTimestep
Definition: Cache.hpp:37
unsigned int cache
Definition: Cache.hpp:42
CacheTS cacheTimestamp
Definition: Cache.hpp:38
double realTimestamp
Definition: Cache.hpp:36
unsigned int reiterate
Definition: Cache.hpp:41
unsigned int dummy
Definition: Cache.hpp:45
unsigned int substep
Definition: Cache.hpp:40
unsigned int numstep
Definition: Cache.hpp:39
unsigned int update
Definition: Cache.hpp:43