Add unit test for all basic data structures.

nanovms / nanos

A kernel designed to run one and only one application in a virtualized environment

https://nanos.org

Apache License 2.0

2.66k stars 137 forks source link

Add unit test for all basic data structures. #184

Open tijoytom-zz opened 6 years ago

tijoytom-zz commented 6 years ago

-bitmap -pqueue -buffer -rtrie ( maybe not for now)

levex commented 6 years ago

Also, assertions (i.e. bitmap->mapbits <= bitmap->maxbits) etc

wjhun commented 5 years ago

id_heap_test is a bitmap allocator test (though could be improved)

starting tasklist, feel free to edit/add:

[x] non-alloc bitmap code
[x] pqueue
[x] tuples (https://github.com/nanovms/nanos/issues/270)
[x] tlog
[x] tfs
[x] buffer / vector(https://github.com/nanovms/nanos/issues/267)
[x] rbtree (pending)
~~futex~~ [this isn't a data structure test, see #1306]
[x] socket (loopback) / poll
[x] queue
[x] random
[x] timer / timer calibration
[x] file r/w
[x] rtrie (https://github.com/nanovms/nanos/issues/268)
[x] table (https://github.com/nanovms/nanos/issues/269)
[ ] formatters (vbprintf, etc)
[ ] merge & refcount (could be rolled into one test as they are similar)
[ ] scatter gather (sg)
[ ] string functions (runtime_str*)
[ ] symbol table (intern, intern_u64 - just test identity and symbol_string)
[ ] timerheap (pqueue is covered, but check timer_service, overrun calculation, etc.)
[ ] mcache (objcache is covered, test wrapper, allocation and total counts, deallocate of -1ull size / free() behavior)

uma-sethuraman commented 4 years ago

Hello, my team members and I are students at the University of Texas at Austin. We are looking to contribute to Nanos as a part of a project for our virtualization class. Could we take on this issue? Would this be a good first issue to tackle?

eyberg commented 4 years ago

sorry just now seeing this, yes please feel free to work on this, i'd just break up individual tests against the various data structures into separate pull requests, please reach out if you need more direction/help

wjhun commented 4 years ago

Hello Uma. This issue is very old and was out-of-date, so I updated it. The only item left here is a unit test for bitmaps. Bitmaps are tested indirectly in the id heap test, but an explicit unit test would still be welcome if you are interested in picking that up.

We need a good futex runtime test, too, but that isn't really a data structure test. I'll open a new issue for that in case you or your colleagues are interested in picking that up (see #1306).

uma-sethuraman commented 4 years ago

Hi Ian and Will, Thank you for the helpful information! My teammates and I will go ahead and start working on this issue. We're also interested in issue #1306 which Will referenced in his reply, so I commented on that issue as well. We'll let you know if we have any additional questions as we start working on this issue.

samantha3pen commented 4 years ago

Hello @eyberg and @wjhun , I'm one of Uma's teammates and I'll be helping with this issue. Thank you for the updates! So far, I've begun to familiarize myself with the bitmap.c and id_heap_test.c files, but I'd appreciate having some more direction/help on where I should start with creating unit tests for bitmaps and what your expectations are.

wjhun commented 4 years ago

Hello @samantha3pen, and thank you for offering to contribute. The id_heap_test unit test exercises the bitmap code somewhat, but this is only a brute-force (randomized) test, and it doesn't exercise the bitmap interface directly (or completely).

A good unit test here should, at least:

test all bitmap functions and macros (like bitmap_foreach) for correct behavior
for functions that return some error result, stress that the correct result is given for a set of inputs (including invalid arguments)
- e.g. bitmap_range_check_and_set should fail if validate is set to true and some bits in the query range have already been set (if set is true) or cleared (if !set).
test for invariant conditions
- e.g. allocations from the bitmap should be aligned to the power-of-2 greater than or equal to the allocation size

There are rules in the build to generate gcov files for the unit tests. These can help verify that your test exercises all paths through conditionals in the bitmap implemenation.

samantha3pen commented 3 years ago

Hi @wjhun , my pr for the bitmap unit tests has recently been merged and I was wondering if there's any more work to be done for this issue?

wjhun commented 3 years ago

Thank you, @samantha3pen, for the contribution. After a quick review I did find more parts of the runtime environment (src/runtime) don't have explicit tests. I added open items for them above.