Sunday 3 December 2017

Open Source Summit NA 2017

The Linux foundation holds a lot of events where companies can reach the maintainers and developers across all the important open source software projects in enterprise, networking, embedded, IoT and cloud infrastructure.

Open Source Summit is the premier open source technical conference in North America, gathering 2,000+ developers, operators and community leadership professionals to collaborate, share information and learn about the latest in open technologies, including Linux, containers, cloud computing and more. This time they also organised a Diversity Summit.


I was really lucky and excited to be a part of the OSS NA 2017. I had sent a proposal earlier in May for delivering a talk based on my Outreachy internship with Linux Kernel from December 2016 - March 2017, which was accepted. The best part was connecting with my mentor Matthew Wilcox as well as a fellow intern who was also my co-speaker for the talk, Sandhya Bankar, though we all missed having Rik Van Riel, also my mentor for the Outreachy internship, and Julia Lawall, who manages and mentors the outreachy internships and has been really encouraging throughout.



With my mentor Matthew Wilcox

With Greg kroah-hartman
Coming to the conference, I had never experienced such a diverse collection of talks, people and organisations as in OSS NA 17. Even the backdrop of Los Angeles, its amazing food and places and wonderful networking opportunities truly made the experience enriching and magical.

With Sandhya Bankar at the partner reception at The Rooftop at The Standard.
At the evening event at Paramount Studios
At the Walt Disney Concert Hall with Jaminy Prabha
I couldn't understand the talks from CloudOpen and ContainerCon tracks much, but going around the sponsor showcase, I got a lot of background on what these very popular and upcoming technologies are about and got inspired to explore them when I go back. I had some very interesting discussions there. I attended many LinuxCon and Diversity track talks as well as keynotes which I found most interesting and took a lot home from them.

At the sponsor showcase with this amazing web representation of all the technologies there.
The opening keynote by Jim Zemlin really set up the excitement about open source and the next 4 days.



Next I really liked knowing about the CHAOSS Project and found it relevant to my research area at college. CHAOSS is a new Linux Foundation project aimed at producing integrated, open source software for analyzing software development, together with defining implementation-agnostic metrics for measuring community activity, contributions, and health.

Another highlight of the first day was the Women in Open Source Lunch sponsored by Intel. The kind of positivity, support, ideas and inspiration in that room was really one of its kind.

Being one of the few students at the summit, I found the talk, "Increasing student participation in open source" very interesting. Similarly the career fair was fun, getting to talk to engineers in popular companies and the job profiles that they are seeking. 

All the keynotes over the rest of the conference were really interesting, but the afternoon talks sometimes required too much attention to really get them and I was jet-lagged.

I particularly enjoyed the keynote by Tanmay Bakshi as well as meeting him and his family later. He talked about how he’s using cognitive and cloud computing to change the world, through his open-source initiatives, for instance, “The Cognitive Story”, meant to augment and amplify human capabilities; and “AskTanmay”, the world’s first Web-Based NLQA System, built using IBM Watson’s Cognitive Capabilities. It was inspiring to learn how passionate he is about technology at such a young age.


A highlight from the third day was my mentor's talk on Replacing the Radix Tree which was a follow-up thread to my outreachy internship and inspired me to contribute to the new XArray API and test suite.

I am grateful to all from the Linux community and all those who support the outreachy internships, and Marina Zhurakhinskaya and Sarah Sharp. I'm also really grateful to The Linux foundation and Outreachy programme for sponsoring my trip.

Friday 20 January 2017

Performance benchmarks in radix tree test suite

Currently we have tests to check performance of tagged or normal iteration, in terms of speed or time of iteration. Let's see how these work.

static void benchmark_size(unsigned long size, unsigned long step, int order)
{
        RADIX_TREE(tree, GFP_KERNEL);
        long long normal, tagged;
        unsigned long index;

        for (index = 0 ; index < size ; index += step) {
                item_insert_order(&tree, index, order);
                radix_tree_tag_set(&tree, index, 0); 
        }

        tagged = benchmark_iter(&tree, true);
        normal = benchmark_iter(&tree, false);

        printf("Size %ld, step %6ld, order %d tagged %10lld ns, normal %10lld ns\n",
                size, step, order, tagged, normal);

        item_kill_tree(&tree);
        rcu_barrier();
}

We start with an arbitrary size of the radix tree say 210 or 220. A step of 128 means that starting from index 0 till the max index i.e. size, every 128th key index will be used to insert a tagged item. Order denotes the number of indices covered by a particular key. So a given key covers 2order indices around it. So if the order is non zero, the step size passed in will be 2order times it.

So we insert an item at every index which is an integral multiple of 'step', between 0 to size, and tag it with TAG 0, then execute tagged followed by normal iteration.

static long long benchmark_iter(struct radix_tree_root *root, bool tagged)
{
        volatile unsigned long sink = 0;
        struct radix_tree_iter iter;
        struct timespec start, finish;
        long long nsec;
        int l, loops = 1;
        void **slot;

#ifdef BENCHMARK
again:
#endif
        clock_gettime(CLOCK_MONOTONIC, &start);
        for (l = 0; l < loops; l++) {
                if (tagged) {
                        radix_tree_for_each_tagged(slot, root, &iter, 0, 0)
                                sink ^= (unsigned long)slot;
                } else {
                        radix_tree_for_each_slot(slot, root, &iter, 0)
                                sink ^= (unsigned long)slot;
                }
        }
        clock_gettime(CLOCK_MONOTONIC, &finish);

        nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
               (finish.tv_nsec - start.tv_nsec);

#ifdef BENCHMARK
        if (loops == 1 && nsec * 5 < NSEC_PER_SEC) {
                loops = NSEC_PER_SEC / nsec / 4 + 1;
                goto again;
        }
#endif

        nsec /= loops;
        return nsec;
}

By default these tests are executed with RADIX_TREE_MAP_SHIFT value of 3, but if we want to get performance comparable to in kernel performance, we can compile using BENCHMARK=1 which sets RADIX_TREE_MAP_SHIFT to 6.

We track the time elapsed for the iteration in nanoseconds in variable nsec. If RADIX_TREE_MAP_SHIFT is 6, i.e. benchmark is 1, we may get nsec too small (less than 0.2th fraction of NSEC_PER_SEC), in which case we want to measure time elapsed for multiple iterations and take the average. The number of iterations is decided by how small nsec initially is. 

Sunday 1 January 2017

Radix Tree Test Suite Regression Test 3

We start by creating two void pointers ptr0 with value 0x4 and ptr with value 0x8.

void *ptr0 = (void *)4ul;
void *ptr = (void *)8ul;

Next we insert the entry ptr0 (0x4) into the tree and tag it with TAG 0.

radix_tree_insert(&root, 0, ptr0);
radix_tree_tag_set(&root, 0, 0);

Now we begin the tagged iteration. We get the first tagged slot 0x4 at index 0, then insert a new item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
        printv(2, "tagged %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                radix_tree_tag_set(&root, 1, 0);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

radix_tree_iter_retry(&iter) works by updating the iter->next_index to iter->index, iter->tags to 0 and slot to NULL, so that the subsequent call to radix_tree_next_slot() returns NULL and the subsequent call to radix_tree_next_chunk() returns the first slot of the chunk associated with iter, which was the slot for which we needed to repeat the look-up.

static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
        if (flags & RADIX_TREE_ITER_TAGGED) {
                iter->tags >>= 1;
                if (unlikely(!iter->tags))
                        return NULL;
...

However, if care is not taken we can get a segfault if we try to de-reference a NULL slot. This is checked with the if (unlikely(!iter->tags)).

Similar is the case with iteration for all non-empty slots via the radix_tree_for_each_slot(). We start with the tree containing only one item (0x4) at index 0. After looking it up we insert another item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_slot(slot, &root, &iter, 0) {
        printv(2, "slot %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

In this case segfault is avoided by proceeding with de-referencing the slot only if radix_tree_chunk_size(iter) returns a positive value.

static __always_inline long
radix_tree_chunk_size(struct radix_tree_iter *iter)
{
        return (iter->next_index - iter->index) >> iter_shift(iter);
}

radix_tree_iter_retry(&iter) works by updating the iter->next_index to iter->index so count is returned as 0 (for 0 order slots).

Similar is the case for iteration over all contiguous slots, until the first empty slot, via the radix_tree_for_each_contig(). We start with the tree containing only one item (0x4) at index 0. After looking it up we insert another item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_contig(slot, &root, &iter, 0) {
        printv(2, "contig %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

In this case segfault is avoided by the following type of check in radix_tree_next_slot() and radix_tree_next_chunk().

if (flags & RADIX_TREE_ITER_CONTIG) {
        /* forbid switching to the next chunk */
        iter->next_index = 0;
        break;
}
...
return NULL;

The next three tests check the same behavior of radix_tree_next_slot() to prevent a segfault, the difference here being that the slot is made NULL by radix_tree_iter_resume().