ua_nodestore_default.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489
  1. /* This work is licensed under a Creative Commons CCZero 1.0 Universal License.
  2. * See http://creativecommons.org/publicdomain/zero/1.0/ for more information.
  3. *
  4. * Copyright 2014-2017 (c) Fraunhofer IOSB (Author: Julius Pfrommer)
  5. * Copyright 2017 (c) Julian Grothoff
  6. * Copyright 2017 (c) Stefan Profanter, fortiss GmbH
  7. */
  8. #include "ua_nodestore_default.h"
  9. /* container_of */
  10. #define container_of(ptr, type, member) \
  11. (type *)((uintptr_t)ptr - offsetof(type,member))
  12. #ifdef UA_ENABLE_MULTITHREADING
  13. #include <pthread.h>
  14. #define BEGIN_CRITSECT(NODEMAP) pthread_mutex_lock(&(NODEMAP)->mutex)
  15. #define END_CRITSECT(NODEMAP) pthread_mutex_unlock(&(NODEMAP)->mutex)
  16. #else
  17. #define BEGIN_CRITSECT(NODEMAP)
  18. #define END_CRITSECT(NODEMAP)
  19. #endif
  20. /* The default Nodestore is simply a hash-map from NodeIds to Nodes. To find an
  21. * entry, iterate over candidate positions according to the NodeId hash.
  22. *
  23. * - Tombstone or non-matching NodeId: continue searching
  24. * - Matching NodeId: Return the entry
  25. * - NULL: Abort the search */
  26. typedef struct UA_NodeMapEntry {
  27. struct UA_NodeMapEntry *orig; /* the version this is a copy from (or NULL) */
  28. UA_UInt16 refCount; /* How many consumers have a reference to the node? */
  29. UA_Boolean deleted; /* Node was marked as deleted and can be deleted when refCount == 0 */
  30. UA_Node node;
  31. } UA_NodeMapEntry;
  32. #define UA_NODEMAP_MINSIZE 64
  33. #define UA_NODEMAP_TOMBSTONE ((UA_NodeMapEntry*)0x01)
  34. typedef struct {
  35. UA_NodeMapEntry **entries;
  36. UA_UInt32 size;
  37. UA_UInt32 count;
  38. UA_UInt32 sizePrimeIndex;
  39. #ifdef UA_ENABLE_MULTITHREADING
  40. pthread_mutex_t mutex; /* Protect access */
  41. #endif
  42. } UA_NodeMap;
  43. /*********************/
  44. /* HashMap Utilities */
  45. /*********************/
  46. /* The size of the hash-map is always a prime number. They are chosen to be
  47. * close to the next power of 2. So the size ca. doubles with each prime. */
  48. static UA_UInt32 const primes[] = {
  49. 7, 13, 31, 61, 127, 251,
  50. 509, 1021, 2039, 4093, 8191, 16381,
  51. 32749, 65521, 131071, 262139, 524287, 1048573,
  52. 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
  53. 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291
  54. };
  55. static UA_UInt32 mod(UA_UInt32 h, UA_UInt32 size) { return h % size; }
  56. static UA_UInt32 mod2(UA_UInt32 h, UA_UInt32 size) { return 1 + (h % (size - 2)); }
  57. static UA_UInt16
  58. higher_prime_index(UA_UInt32 n) {
  59. UA_UInt16 low = 0;
  60. UA_UInt16 high = (UA_UInt16)(sizeof(primes) / sizeof(UA_UInt32));
  61. while(low != high) {
  62. UA_UInt16 mid = (UA_UInt16)(low + ((high - low) / 2));
  63. if(n > primes[mid])
  64. low = (UA_UInt16)(mid + 1);
  65. else
  66. high = mid;
  67. }
  68. return low;
  69. }
  70. /* returns an empty slot or null if the nodeid exists or if no empty slot is found. */
  71. static UA_NodeMapEntry **
  72. findFreeSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  73. UA_NodeMapEntry **retval = NULL;
  74. UA_UInt32 h = UA_NodeId_hash(nodeid);
  75. UA_UInt32 size = ns->size;
  76. UA_UInt64 idx = mod(h, size); // use 64 bit container to avoid overflow
  77. UA_UInt32 startIdx = (UA_UInt32)idx;
  78. UA_UInt32 hash2 = mod2(h, size);
  79. UA_NodeMapEntry *entry = NULL;
  80. do {
  81. entry = ns->entries[(UA_UInt32)idx];
  82. if(entry > UA_NODEMAP_TOMBSTONE &&
  83. UA_NodeId_equal(&entry->node.nodeId, nodeid))
  84. return NULL;
  85. if(!retval && entry <= UA_NODEMAP_TOMBSTONE)
  86. retval = &ns->entries[(UA_UInt32)idx];
  87. idx += hash2;
  88. if(idx >= size)
  89. idx -= size;
  90. } while((UA_UInt32)idx != startIdx && entry);
  91. /* NULL is returned if there is no free slot (idx == startIdx).
  92. * Otherwise the first free slot is returned after we are sure,
  93. * that the node id cannot be found in the used hashmap (!entry). */
  94. return retval;
  95. }
  96. /* The occupancy of the table after the call will be about 50% */
  97. static UA_StatusCode
  98. expand(UA_NodeMap *ns) {
  99. UA_UInt32 osize = ns->size;
  100. UA_UInt32 count = ns->count;
  101. /* Resize only when table after removal of unused elements is either too
  102. full or too empty */
  103. if(count * 2 < osize && (count * 8 > osize || osize <= UA_NODEMAP_MINSIZE))
  104. return UA_STATUSCODE_GOOD;
  105. UA_NodeMapEntry **oentries = ns->entries;
  106. UA_UInt32 nindex = higher_prime_index(count * 2);
  107. UA_UInt32 nsize = primes[nindex];
  108. UA_NodeMapEntry **nentries = (UA_NodeMapEntry **)UA_calloc(nsize, sizeof(UA_NodeMapEntry*));
  109. if(!nentries)
  110. return UA_STATUSCODE_BADOUTOFMEMORY;
  111. ns->entries = nentries;
  112. ns->size = nsize;
  113. ns->sizePrimeIndex = nindex;
  114. /* recompute the position of every entry and insert the pointer */
  115. for(size_t i = 0, j = 0; i < osize && j < count; ++i) {
  116. if(oentries[i] <= UA_NODEMAP_TOMBSTONE)
  117. continue;
  118. UA_NodeMapEntry **e = findFreeSlot(ns, &oentries[i]->node.nodeId);
  119. UA_assert(e);
  120. *e = oentries[i];
  121. ++j;
  122. }
  123. UA_free(oentries);
  124. return UA_STATUSCODE_GOOD;
  125. }
  126. static UA_NodeMapEntry *
  127. newEntry(UA_NodeClass nodeClass) {
  128. size_t size = sizeof(UA_NodeMapEntry) - sizeof(UA_Node);
  129. switch(nodeClass) {
  130. case UA_NODECLASS_OBJECT:
  131. size += sizeof(UA_ObjectNode);
  132. break;
  133. case UA_NODECLASS_VARIABLE:
  134. size += sizeof(UA_VariableNode);
  135. break;
  136. case UA_NODECLASS_METHOD:
  137. size += sizeof(UA_MethodNode);
  138. break;
  139. case UA_NODECLASS_OBJECTTYPE:
  140. size += sizeof(UA_ObjectTypeNode);
  141. break;
  142. case UA_NODECLASS_VARIABLETYPE:
  143. size += sizeof(UA_VariableTypeNode);
  144. break;
  145. case UA_NODECLASS_REFERENCETYPE:
  146. size += sizeof(UA_ReferenceTypeNode);
  147. break;
  148. case UA_NODECLASS_DATATYPE:
  149. size += sizeof(UA_DataTypeNode);
  150. break;
  151. case UA_NODECLASS_VIEW:
  152. size += sizeof(UA_ViewNode);
  153. break;
  154. default:
  155. return NULL;
  156. }
  157. UA_NodeMapEntry *entry = (UA_NodeMapEntry*)UA_calloc(1, size);
  158. if(!entry)
  159. return NULL;
  160. entry->node.nodeClass = nodeClass;
  161. return entry;
  162. }
  163. static void
  164. deleteEntry(UA_NodeMapEntry *entry) {
  165. UA_Node_deleteMembers(&entry->node);
  166. UA_free(entry);
  167. }
  168. static void
  169. cleanupEntry(UA_NodeMapEntry *entry) {
  170. if(entry->deleted && entry->refCount == 0)
  171. deleteEntry(entry);
  172. }
  173. static UA_StatusCode
  174. clearSlot(UA_NodeMap *ns, UA_NodeMapEntry **slot) {
  175. (*slot)->deleted = true;
  176. cleanupEntry(*slot);
  177. *slot = UA_NODEMAP_TOMBSTONE;
  178. --ns->count;
  179. /* Downsize the hashmap if it is very empty */
  180. if(ns->count * 8 < ns->size && ns->size > 32)
  181. expand(ns); /* Can fail. Just continue with the bigger hashmap. */
  182. return UA_STATUSCODE_GOOD;
  183. }
  184. static UA_NodeMapEntry **
  185. findOccupiedSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  186. UA_UInt32 h = UA_NodeId_hash(nodeid);
  187. UA_UInt32 size = ns->size;
  188. UA_UInt64 idx = mod(h, size); // use 64 bit container to avoid overflow
  189. UA_UInt32 hash2 = mod2(h, size);
  190. UA_UInt32 startIdx = (UA_UInt32)idx;
  191. UA_NodeMapEntry *entry = NULL;
  192. do {
  193. entry = ns->entries[(UA_UInt32)idx];
  194. if(entry > UA_NODEMAP_TOMBSTONE &&
  195. UA_NodeId_equal(&entry->node.nodeId, nodeid))
  196. return &ns->entries[(UA_UInt32)idx];
  197. idx += hash2;
  198. if(idx >= size)
  199. idx -= size;
  200. } while((UA_UInt32)idx != startIdx && entry);
  201. /* NULL is returned if there is no free slot (idx == startIdx)
  202. * and the node id is not found or if the end of the used slots (!entry)
  203. * is reached. */
  204. return NULL;
  205. }
  206. /***********************/
  207. /* Interface functions */
  208. /***********************/
  209. static UA_Node *
  210. UA_NodeMap_newNode(void *context, UA_NodeClass nodeClass) {
  211. UA_NodeMapEntry *entry = newEntry(nodeClass);
  212. if(!entry)
  213. return NULL;
  214. return &entry->node;
  215. }
  216. static void
  217. UA_NodeMap_deleteNode(void *context, UA_Node *node) {
  218. #ifdef UA_ENABLE_MULTITHREADING
  219. UA_NodeMap *ns = (UA_NodeMap*)context;
  220. #endif
  221. BEGIN_CRITSECT(ns);
  222. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  223. UA_assert(&entry->node == node);
  224. deleteEntry(entry);
  225. END_CRITSECT(ns);
  226. }
  227. static const UA_Node *
  228. UA_NodeMap_getNode(void *context, const UA_NodeId *nodeid) {
  229. UA_NodeMap *ns = (UA_NodeMap*)context;
  230. BEGIN_CRITSECT(ns);
  231. UA_NodeMapEntry **entry = findOccupiedSlot(ns, nodeid);
  232. if(!entry) {
  233. END_CRITSECT(ns);
  234. return NULL;
  235. }
  236. ++(*entry)->refCount;
  237. END_CRITSECT(ns);
  238. return (const UA_Node*)&(*entry)->node;
  239. }
  240. static void
  241. UA_NodeMap_releaseNode(void *context, const UA_Node *node) {
  242. if (!node)
  243. return;
  244. #ifdef UA_ENABLE_MULTITHREADING
  245. UA_NodeMap *ns = (UA_NodeMap*)context;
  246. #endif
  247. BEGIN_CRITSECT(ns);
  248. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  249. UA_assert(&entry->node == node);
  250. UA_assert(entry->refCount > 0);
  251. --entry->refCount;
  252. cleanupEntry(entry);
  253. END_CRITSECT(ns);
  254. }
  255. static UA_StatusCode
  256. UA_NodeMap_getNodeCopy(void *context, const UA_NodeId *nodeid,
  257. UA_Node **outNode) {
  258. UA_NodeMap *ns = (UA_NodeMap*)context;
  259. BEGIN_CRITSECT(ns);
  260. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  261. if(!slot) {
  262. END_CRITSECT(ns);
  263. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  264. }
  265. UA_NodeMapEntry *entry = *slot;
  266. UA_NodeMapEntry *newItem = newEntry(entry->node.nodeClass);
  267. if(!newItem) {
  268. END_CRITSECT(ns);
  269. return UA_STATUSCODE_BADOUTOFMEMORY;
  270. }
  271. UA_StatusCode retval = UA_Node_copy(&entry->node, &newItem->node);
  272. if(retval == UA_STATUSCODE_GOOD) {
  273. newItem->orig = entry; // store the pointer to the original
  274. *outNode = &newItem->node;
  275. } else {
  276. deleteEntry(newItem);
  277. }
  278. END_CRITSECT(ns);
  279. return retval;
  280. }
  281. static UA_StatusCode
  282. UA_NodeMap_removeNode(void *context, const UA_NodeId *nodeid) {
  283. UA_NodeMap *ns = (UA_NodeMap*)context;
  284. BEGIN_CRITSECT(ns);
  285. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  286. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  287. if(slot)
  288. retval = clearSlot(ns, slot);
  289. else
  290. retval = UA_STATUSCODE_BADNODEIDUNKNOWN;
  291. END_CRITSECT(ns);
  292. return retval;
  293. }
  294. static UA_StatusCode
  295. UA_NodeMap_insertNode(void *context, UA_Node *node,
  296. UA_NodeId *addedNodeId) {
  297. UA_NodeMap *ns = (UA_NodeMap*)context;
  298. BEGIN_CRITSECT(ns);
  299. if(ns->size * 3 <= ns->count * 4) {
  300. if(expand(ns) != UA_STATUSCODE_GOOD) {
  301. END_CRITSECT(ns);
  302. return UA_STATUSCODE_BADINTERNALERROR;
  303. }
  304. }
  305. UA_NodeMapEntry **slot;
  306. if(node->nodeId.identifierType == UA_NODEIDTYPE_NUMERIC &&
  307. node->nodeId.identifier.numeric == 0) {
  308. /* create a random nodeid */
  309. /* start at least with 50,000 to make sure we don not conflict with nodes from the spec */
  310. /* if we find a conflict, we just try another identifier until we have tried all possible identifiers */
  311. /* since the size is prime and we don't change the increase val, we will reach the starting id again */
  312. /* E.g. adding a nodeset will create children while there are still other nodes which need to be created */
  313. /* Thus the node ids may collide */
  314. UA_UInt32 size = ns->size;
  315. UA_UInt64 identifier = mod(50000 + size+1, size); // start value, use 64 bit container to avoid overflow
  316. UA_UInt32 increase = mod2(ns->count+1, size);
  317. UA_UInt32 startId = (UA_UInt32)identifier; // mod ensures us that the id is a valid 32 bit
  318. do {
  319. node->nodeId.identifier.numeric = (UA_UInt32)identifier;
  320. slot = findFreeSlot(ns, &node->nodeId);
  321. if(slot)
  322. break;
  323. identifier += increase;
  324. if(identifier >= size)
  325. identifier -= size;
  326. } while((UA_UInt32)identifier != startId);
  327. if (!slot) {
  328. END_CRITSECT(ns);
  329. return UA_STATUSCODE_BADOUTOFMEMORY;
  330. }
  331. } else {
  332. slot = findFreeSlot(ns, &node->nodeId);
  333. if(!slot) {
  334. deleteEntry(container_of(node, UA_NodeMapEntry, node));
  335. END_CRITSECT(ns);
  336. return UA_STATUSCODE_BADNODEIDEXISTS;
  337. }
  338. }
  339. *slot = container_of(node, UA_NodeMapEntry, node);
  340. ++ns->count;
  341. UA_assert(&(*slot)->node == node);
  342. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  343. if(addedNodeId) {
  344. retval = UA_NodeId_copy(&node->nodeId, addedNodeId);
  345. if(retval != UA_STATUSCODE_GOOD)
  346. clearSlot(ns, slot);
  347. }
  348. END_CRITSECT(ns);
  349. return retval;
  350. }
  351. static UA_StatusCode
  352. UA_NodeMap_replaceNode(void *context, UA_Node *node) {
  353. UA_NodeMap *ns = (UA_NodeMap*)context;
  354. BEGIN_CRITSECT(ns);
  355. UA_NodeMapEntry **slot = findOccupiedSlot(ns, &node->nodeId);
  356. if(!slot) {
  357. END_CRITSECT(ns);
  358. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  359. }
  360. UA_NodeMapEntry *newEntryContainer = container_of(node, UA_NodeMapEntry, node);
  361. if(*slot != newEntryContainer->orig) {
  362. /* The node was updated since the copy was made */
  363. deleteEntry(newEntryContainer);
  364. END_CRITSECT(ns);
  365. return UA_STATUSCODE_BADINTERNALERROR;
  366. }
  367. (*slot)->deleted = true;
  368. cleanupEntry(*slot);
  369. *slot = newEntryContainer;
  370. END_CRITSECT(ns);
  371. return UA_STATUSCODE_GOOD;
  372. }
  373. static void
  374. UA_NodeMap_iterate(void *context, void *visitorContext,
  375. UA_NodestoreVisitor visitor) {
  376. UA_NodeMap *ns = (UA_NodeMap*)context;
  377. BEGIN_CRITSECT(ns);
  378. for(UA_UInt32 i = 0; i < ns->size; ++i) {
  379. if(ns->entries[i] > UA_NODEMAP_TOMBSTONE) {
  380. END_CRITSECT(ns);
  381. UA_NodeMapEntry *entry = ns->entries[i];
  382. entry->refCount++;
  383. visitor(visitorContext, &entry->node);
  384. entry->refCount--;
  385. cleanupEntry(entry);
  386. BEGIN_CRITSECT(ns);
  387. }
  388. }
  389. END_CRITSECT(ns);
  390. }
  391. static void
  392. UA_NodeMap_delete(void *context) {
  393. UA_NodeMap *ns = (UA_NodeMap*)context;
  394. #ifdef UA_ENABLE_MULTITHREADING
  395. pthread_mutex_destroy(&ns->mutex);
  396. #endif
  397. UA_UInt32 size = ns->size;
  398. UA_NodeMapEntry **entries = ns->entries;
  399. for(UA_UInt32 i = 0; i < size; ++i) {
  400. if(entries[i] > UA_NODEMAP_TOMBSTONE) {
  401. /* On debugging builds, check that all nodes were release */
  402. UA_assert(entries[i]->refCount == 0);
  403. /* Delete the node */
  404. deleteEntry(entries[i]);
  405. }
  406. }
  407. UA_free(ns->entries);
  408. UA_free(ns);
  409. }
  410. UA_StatusCode
  411. UA_Nodestore_default_new(UA_Nodestore *ns) {
  412. /* Allocate and initialize the nodemap */
  413. UA_NodeMap *nodemap = (UA_NodeMap*)UA_malloc(sizeof(UA_NodeMap));
  414. if(!nodemap)
  415. return UA_STATUSCODE_BADOUTOFMEMORY;
  416. nodemap->sizePrimeIndex = higher_prime_index(UA_NODEMAP_MINSIZE);
  417. nodemap->size = primes[nodemap->sizePrimeIndex];
  418. nodemap->count = 0;
  419. nodemap->entries = (UA_NodeMapEntry**)
  420. UA_calloc(nodemap->size, sizeof(UA_NodeMapEntry*));
  421. if(!nodemap->entries) {
  422. UA_free(nodemap);
  423. return UA_STATUSCODE_BADOUTOFMEMORY;
  424. }
  425. #ifdef UA_ENABLE_MULTITHREADING
  426. pthread_mutex_init(&nodemap->mutex, NULL);
  427. #endif
  428. /* Populate the nodestore */
  429. ns->context = nodemap;
  430. ns->deleteNodestore = UA_NodeMap_delete;
  431. ns->inPlaceEditAllowed = true;
  432. ns->newNode = UA_NodeMap_newNode;
  433. ns->deleteNode = UA_NodeMap_deleteNode;
  434. ns->getNode = UA_NodeMap_getNode;
  435. ns->releaseNode = UA_NodeMap_releaseNode;
  436. ns->getNodeCopy = UA_NodeMap_getNodeCopy;
  437. ns->insertNode = UA_NodeMap_insertNode;
  438. ns->replaceNode = UA_NodeMap_replaceNode;
  439. ns->removeNode = UA_NodeMap_removeNode;
  440. ns->iterate = UA_NodeMap_iterate;
  441. return UA_STATUSCODE_GOOD;
  442. }