iondbproject / iondb

IonDB, a key-value datastore for resource constrained systems.
BSD 3-Clause "New" or "Revised" License
587 stars 48 forks source link

TODO: This is a potential issue and needs to be tested on SAMD3 #101

Open danaack opened 7 years ago

danaack commented 7 years ago

https://github.com/iondbproject/iondb/blob/development/src/dictionary/dictionary.c#L198-L207 https://github.com/iondbproject/iondb/blob/development/src/dictionary/dictionary.c#L248-L256

Jonas-Meyer97 commented 6 years ago

I have an Arduino Due(SAM3X8E) and i have some wired behavior im not sure if its related to the potential issue you described. My Arduino Uno(ATmega328P) seems to work just fine. On the Due i can only read the first entry i inserted. All the others readings return err_item_not_found.

#define __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__
#define __ORDER_LITTLE_ENDIAN__ 1234
#include <IonDB.h>

void setup() 
{
  Serial.begin(9600);
  Serial.println("Hello World!");

  Dictionary < int, int > *dict = new SkipList < int, int > (-1, key_type_numeric_signed, sizeof(int), sizeof(int), 7);

  dict->insert(3, 10);
  dict->insert(4, 16);
  dict->insert(5, 20);

  int value = dict->get(3);

  if(dict->last_status.error != err_ok)
  {
    Serial.println("3Something went wrong!");
    if(dict->last_status.error == err_item_not_found)
    {
      Serial.println("\tItem was not found");
    }
  }

  Serial.print("3 -> ");
  Serial.println(value);

  int newValue = dict->get(4);

  if(dict->last_status.error != err_ok)
  {
    Serial.println("4Somethign went wrong!");
    if(dict->last_status.error == err_item_not_found)
    {
      Serial.println("\tItem was not found");
    }
  }

  Serial.print("4 -> ");
  Serial.println(newValue);

}

void loop() 
{

}

Arduino Due:

Hello World!
3 -> 10
4Somethign went wrong!
    Item was not found
4 -> 0

Arduino Uno:

Hello World!
3 -> 10
4 -> 16

Im not sure whats the acutall problem is. Your second links seems to show some problem with endian. Also i saw here that the Due has some problem on this topic. I tried to add some lines before the include of iondb like this #define __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__ but it did not change anything. Any idea what causes this behavior?

CowBoy4mH3LL commented 3 years ago

I have the same issue on a Teensy 3.6 board. Except in the setup part it comes out fine but if get is issued in the loop it issues the error as shown above. Dictionary is global in this case.

margaretselzer commented 3 years ago

I have very similar issues on Due. Tried to play around with byte order defines, but nothing changed. When using SkipList it is possible to insert records and the all records query returns all of them. However with get and equality query only the first record is returned, all else fails. Insert works, but judging from the return of the all record query, the added keys are always placed on the end of the list and I think in a properly functioning list they would be added ordered (between the biggest smaller and the smallest bigger existing key). Update and delete - as expected - only works on the first element in the list. Interestingly it is possible to delete the whole list if one keeps deleting the fist element (as returned by the all records query). Range query also only works for the first element, but only if the upper limit is exactly the same as the key of the first element. In all other cases the range query returns nothing.

When tried OpenAddressHash, even the initial inserts do not work. I get back as many records for the all records query that is defined as dictionary size, and all of the returned keys and values are random numbers reflecting uninitialized memory space. Something seems to be fundamentally wrong with how the memory is managed.

It might be relevant to mention, that I could not get anything to work through the cpp wrapper. That is Dictionary<int, int>* dict = new SkipList<int, int>(0, key_type_numeric_signed, sizeof(int), sizeof(int), 10); produced at least a dictionary object that I could somewhat process, but SkipList<int, int>* dict = SkipList<int, int>::openDictionary(config, type, val); made the Due bord freeze.

None of the file based versions worked on any level. It may be due to the fact that I tried to use the SdFat library instead of the "default" SD library, but as I could never verify correct functioning with memory based versions, it is a moot point.

It feels like the solution is something trivial - e.g. a define at the right place could bring the memory management logic back to working. Unfortunately after 4 days of trying I need to abandon my attempt to make it work as writing my own db at this point feels a safer bet than investing more time in this, especially that it seems nothing really happened in the past 3 years with this project.

It's a shame though... it felt so close. :(

ArduinoMKR commented 2 years ago

Hi, I also had troubles even with the provided BasicUsage example on 32-bit Arduino MKR series (SAMD21), instead with 8-bit Arduino UNO everything works fine. Finally I got the solution for me, at least with the SkipList I am interested in.

First I found, that the keys in the list should be stored in an ascending order by the "sl_insert" routine regardless in which order they were inserted before. With the UNO it works fine, but with the MKR they are just stored in the order they were inserted. You can have a look on all values you have stored within the SkipList with a defined Cursor in your sketch and then using "dict-->allRecords()". They have to be shown in an ascending order.

So I found, that there is something wrong with the insert routine and I had a closer look on it. The thing is simply the following: The decision where to insert a KV pair with the so called "vanilla insert" (= "insert before") doesn't work on SAMD, because the return value of the compare function is defined as an an unsigned 8 bit CHAR. So far, so good, but the further processing needs to interprete the return value as a SIGNED-type (-1/smaller, 0/equal, 1/greater). As the value (-1/smaller) is returned (in 8 bit) as "255" the comparison for example in skip_list.c in line 191 leads to a misinterpretation because "255" is on 32-bit SAMD not seen as (-1) but as "255" and this is greater than 0. On 8-bit AVR/UNO this mechanism works.

You can see this in sl_insert on Line 191: _while (NULL != cursor->next[h] && skiplist->super.compare(key, cursor->next[h]->key, keysize) >= 0) --> return_value 255 leads to "true" where it shoudn't because (-1) is intended

Same effect on line 326 in the sl_find_node routine.

You are done with a simple typecast on this two lines (191, 326) if you are only interested in the skipList (int8_t) _skiplist->super.compare(key, cursor->next[h]->key, keysize) >= 0)

I did it in a more central way, so I changed the return types of the compare functions from char to int8_t in:

Surely there may be better solutions but for me in practice it works.

Hope I could help a little bit Giorgio

ArduinoMKR commented 2 years ago

margaretselzer wrote:

It feels like the solution is something trivial - e.g. .......

Your feeling is right :-) I got the FileBasedUsage example running on an Arduino MKR with MKR Mem Shield, with my modification mentioned above and with a simple modification as follows:

In the file _ionDB/src/file/sd_stdio_ciface.cpp You need to change line 153 from: _operation = FILEWRITE; to: _operation = (O_RDWR | OCREAT); That's all.

Why? The reason is, that the FILE_WRITE definition in the "default" SD library includes _OAPPEND as well, but in that mode the fseek mechanism isn't applicable for writing to an arbitrary position, so leave it away. See also e.g.: https://stackoverflow.com/questions/10631862/fseek-does-not-work-when-file-is-opened-in-a-append-mode

margaretselzer commented 2 years ago

Unfortunately this is not it. Probably my fault that I was not clear enough in my original post, but the symptoms that I describe has nothing to do with files. They were all the memory based versions. I explicitly write that the file based versions did not work on any level. Well, in case of files your solution might be a step forward, but if the memory based version is not working then there are some other issues at play.

ArduinoMKR commented 2 years ago

They were all the memory based versions...

Yes, I got your point. And because of this I wrote in my last post from 22. May "with my modification above". Above should mean a relation to my post from 2 Apr. where I described how I got the SkipList working properly with Equality and Range on Arduino MKR with the BasicUsage example. It's about a problem with variable types which needs to be corrected. Sorry for my unclearity in my last post.