RXDSK is a project currently in development which is worth checking out and keeping an eye on.

It is quiet similar to ZRAM (previously compache) and TMPFS/RAMFS but has some minor differences which renders it more flexible for generic usage.

ZXDSK allows for example an export of the ram disk to a physical disk, making it therefore usable as a swap device. According to the developer, LZO is planned to be used as a compression layer, making it therefore quiet similar in this light to ZRAM. However as opposed to the latter, RXDSK acts as a sort of sparse device, since the defined device size is allocated as the filesystem is growing and not statically as with ZRAM.

To get more information, visit - till then, RXDSK can easily become the defacto ram device choice for RRD base collectors such as Ganglia, Cacti - offloading mysql cache to RXDSK with a persistent enabled sync storage on an SSD drive etc.

Enjoy ;-)

I have created a working Red Hat/CentOS 6 Xen Dom0 Kernel including backport patches. I had to hack to the blktap driver hooks to finalize support of the module due to the interface changes in the recent vanilla kernel. But all is working.

1
2
3
4
5

[root@blackhole1 ~]# uname -rsm
Linux 2.6.32-131.12.1.el6.alouche.xen.dom0.x86_64 x86_64
[root@blackhole1 ~]# xm list
Name                                        ID   Mem VCPUs      State   Time(s)
Domain-0                                     0  1024     4     r-----    235.5

For download of the RPMs or mirror use, see [http://mirror.alouche.net/centos/el6/xen/x8664/](http://mirror.alouche.net/centos/el6/xen/x8664/)

Please note this isn’t a vanilla kernel with Xen support, but the 2.6.32 Red Hat 6 kernel, which has been heavily lacking across all generic redhat/centos mirrors. But it was a necessity for me to have the available patched redhat drivers and kernel tweaks, which makes this kernel more suited and easily ready for production systems.

I do not promise that I will undergo this work for any new Red Hat kernel revision and no guarantee comes with it.

Enjoy,

If you are not familiar with the Mathis Equation, I recommend you quickly go over my post article Mathis Equation and TCP Performance. This is necessary since the Padhye et. al. Equation is an extension to the Mathis Equation for accuracy of TCP throughput calculation over multiple scenario of packet loss.

As simply put, the Padhye et. al. Equation Equation is exactly the same concept as the Mathis Equation but taking in consideration the Maximum TCP Window size affected by received/lost/duplicate ACK, the initial retransmit timer and the effect of the TCP timeout mechanism on the total throughput.

The approximative equation model deferred by a 2 conditional throughput equation as to whether $W\left (p \right ) < Wmax$ or not is

First of all, it is important to keep in mind that Padhye et. al.’s formula relays on the concept that the Windows size ( $W$) increases per $W+ 1/b$ “(b) being the number of packets acknowledge per each received ACK”.

(b) Some hosts send an ack for each X amount of packet received depending on the ACK delay value. For most configuration, an ACK is sent for each 2 packets received.

“Padhye” study centers around different models and scenarios, for instance, packet lost is accounted when triple ack are received and the Window Size of the sender remains un-influenced by the window scaling etc.

Keep in mind that these scenarios do not take for most part some of the TCP model features such as Fast Recovery or the Sender window adjustment by the receiver’s advertised window size. The Padhye equation is one of many models used these days to calculate the TCP throughput.

For more information, refer to the whitepaper @ http://www.sigcomm.org/sigcomm98/tp/paper25.pdf

Hi there!

I have just released version 0.5 of pwgen, which has been refactored to be Firefox 5 compliant.

For those who wishes to use the addon prior to the review from Firefox Mods, you can download the version .

Russian and Polish languages have been added - Thanks to Artem Karpenko [email protected] (RU) and Slawomir Dal - [email protected] (PL).

KSM, simply put is a service daemon which scans the page addresses to find duplicate pages, merges them and therefore reduces the memory density. The code used in this post as example can be found under /mm/ksm.c in the kernel source.

Before continuing, it is important to keep in mind that:

• KSM uses a red-black tree for the stable and unstable trees - efficiency is $O(\log\ n)$ per tree since the height can never be more than $(2log\ (n+1))$ with n being the number of nodes.
• KSM only scans anonymous pages, file backed pages such as HugePages are not scanned and cannot be merged by KSM. This is different to Transparent Huge pages where as in RedHat 6.1, KSM will break up THP into small pages if shareable 4K pages are found and only if the system is running out of memory.
• Merged pages are read-only as they are CoW protected.
• Userspace application can register candidate regions for merging through the system call. We will not tackle the KSM API details in this post.
• Because of the CoW nature, a merged page write action by an application will raise a page fault, which in return triggers the break_cow() routine, which issue a copy of the merged page to the writing application.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static void break_cow(struct rmap_item *rmap_item)
{
         struct mm_struct *mm = rmap_item->mm;
         unsigned long addr = rmap_item->address;
         struct vm_area_struct *vma;

  /*
  * It is not an accident that whenever we want to break COW
  * to undo, we also need to drop a reference to the anon_vma.
  */
         put_anon_vma(rmap_item->anon_vma);

         down_read(&mm->mmap_sem);
         if (ksm_test_exit(mm))
                 goto out;
         vma = find_vma(mm, addr);
         if (!vma || vma->vm_start > addr)
                 goto out;
         if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
                 goto out;
         break_ksm(vma, addr);
 out:
         up_read(&mm->mmap_sem);
 }

With this in mind, here is a summarized view on how KSM works per steps

KSM scan pages and elects whether a page could be considered to be merged… these pages are referred as “candidate” pages. To quickly state it, a candidate page which does not exists in the stable tree is added as a node to the unstable tree, but we will get to this later in the post. To determine if a page has changed or not, KSM relies on a 32bit checksum, which is then added to the page content and evaluated on the next scan.

1
2
3
4
5
6
7
8

static u32 calc_checksum(struct page *page)
{
         u32 checksum;
         void *addr = kmap_atomic(page, KM_USER0);
         checksum = jhash2(addr, PAGE_SIZE / 4, 17);
         kunmap_atomic(addr, KM_USER0);
         return checksum;
}

In other words, KSM finds page X, creates a checksum, stores it in page X - on the next scan, if the checksum of page X did not change, then it is considered as a candidate page.

For each candidate page, KSM starts a memcmp_pages() operation to the stable tree which contains the merged pages.

1
2
3
4
5
6
7
8
9
10
11
12

static int memcmp_pages(struct page *page1, struct page *page2)
{
         char *addr1, *addr2;
         int ret;

         addr1 = kmap_atomic(page1, KM_USER0);
         addr2 = kmap_atomic(page2, KM_USER1);
         ret = memcmp(addr1, addr2, PAGE_SIZE);
         kunmap_atomic(addr2, KM_USER1);
         kunmap_atomic(addr1, KM_USER0);
         return ret;
 }

This unique process is as follow:

1
2
3
4
5
6
7
8
9
10

ret = memcmp_pages(page, tree_page);

if (ret < 0) {
  put_page(tree_page);
node = node->rb_left;
} else if (ret > 0) {
put_page(tree_page);
node = node->rb_right;
} else
return tree_page;

Understanding the following requires an understanding of how a binary tree works in general, more specifically how a red-black tree works.

The stable tree is walked left if the candidate page is less than the page in the stable tree, right if the candidate page is superior to the stable page and the page is simply merge and the candidate page freed if both pages are identical.

The stable tree search function is referenced at http://lxr.free-electrons.com/source/mm/ksm.c#L985

Now if the candidate page was not found in the stable tree, its checksum is re-computed to determine whether the data has changed since or not. If it has changed it is then ignored; if not, the searching process continues in the unstable tree as with the search in the stable tree. The recursion __unstable_tree_search_insert() __can be seen at http://lxr.free-electrons.com/source/mm/ksm.c#L1078.

While searching the unstable tree, KSM will create a new node in this binary tree if the candidate page is unique

1
2
3
4

rmap_item->address |= UNSTABLE_FLAG;
rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK);
rb_link_node(&rmap_item->node, parent, new);
rb_insert_color(&rmap_item->node, &root_unstable_tree);

and if not unique such as the unstable tree contains similar candidate pages, it will be merged to the existing similar node and moved to the stable tree.

Once the KSM scan is done, the unstable tree is destroyed and recreated on the next iteration

I hope that was informative.

Cheers,

Ali

After spending 2 relaxing weeks abroad with crazy dolphins

[slideshow id=1]

here are 2 small changes to the blog:

Introduction of short FAQ Posts

One could easily say that my blogging activity has been a logarithmic decrease per individual months ;-). Having not enough time to write lengthly posts, I will resort to write some FAQ related posts, short in length and to the point. Lengthly posts will still be on the menu but at least the blog will not be that periodically vacant as it has been ;-)

Topic Changes - CS Topics

So far the blog has focus mainly on Network and Unix related stuff, I will be starting soon to discuss generic Computer Science related matters (Algorithms etc.) that touches in both Unix and Network areas and also potentially introducing the readers to general computer science related matters.

That’s all for now ;-)

KGPU is a project that aims to port GPU capabilities directly to the linux kernel. Utilizing CUDA or OpenCL, userspace application can offload calculations to the GPU card, however KGPU extends this now transparently to the kernel.

As stated by the project’s site

The idea behind KGPU is to treat the GPU as a computing co-processor for the operating system, enabling data-parallel computation inside the Linux kernel. This allows us to use SIMD (or SIMT in CUDA) style code to accelerate Linux kernel functionality, and to bring new functionality formerly considered too compute intensive into the kernel. Simply put, KGPU enables vector computing for the kernel.

KGPU is currently developed by the university of Utah and sponsored by NVIDIA.

For more information: and https://github.com/wbsun/kgpu

A great presentation by Ilaj Grigorik

Intelligent Ruby: Getting Started with Machine Learning from Ilya Grigorik on Vimeo.

I have been toying with Koji ( A build server by Fedora) and encountered an issue while starting the kojid daemon on one of the builder host.

1
2

[root@builder1 ~]# /etc/init.d/kojid status
kojid dead but subsys locked

while the log kept showing

1

[INFO] koji.build: Starting up

Time for some debugging, I issue

1

[root@builder1 ~]# /usr/sbin/kojid --verbose --fg

and see

1
2
3
4
5
6
7
8
9
10

koji.AuthError: Traceback (most recent call last):` koji.AuthError: Traceback (most recent call last):
File "/usr/share/koji-hub/kojixmlrpc.py", line 191, in _marshaled_dispatch
response = self._dispatch(method, params)
File "/usr/share/koji-hub/kojixmlrpc.py", line 253, in _dispatch
ret = func(*params,**opts)
File "/usr/share/koji-hub/kojihub.py", line 9005, in getID
host = Host()
File "/usr/share/koji-hub/kojihub.py", line 8811, in __init__
raise koji.AuthError, "No host specified"
AuthError: No host specified

Aha! “AuthError: No host specified” - kojid is complaining that no host was specified! But wait a minute, the “user” directive is correctly specified in the the kojid.conf file

Let’s check

1
2

[root@builder1 ~]# awk /builder1$/ /etc/kojid/kojid.conf
user=builder1

Hmm… time to check the host registered in koji

1
2
3
4

[root@hub ~]# su - kojiadmin
[kojiadmin@hub ~]$ koji list-hosts
Hostname                     Enb Rdy Load/Cap Arches           Last Update
builder1                   Y   N    0.0/2.0 x86_64      -

All good. Let’s check our host certificate

1
2
3
4
5
6
7

[root@hub koji]# openssl x509 -in certs/builder1.crt -noout -text
Certificate:
Data:
Version: 3 (0x2)
Serial Number: 9 (0x9)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=XX, ST=XX, L=XX, O=XX, CN=builder1.domain.local

Only obvious different is that I have use a FQDN as a CN in the certificate (good!), could it be that kojid isn’t expanding the hostname user to a FQDN?

Let’s remove the current builder and re-add it as a FQDN as I am not able to add “builder1.domain.local” since it already exists as a user in the users table of the koji database and this is creating a key violation constraint as follow:

1
2

[kojiadmin@builder1 ~]$ koji add-host builder1.domain.local x86_64
Fault: 'pg.DatabaseError: error \'ERROR:  duplicate key violates unique constraint "users_name_key"\n\' in \'INSERT INTO users (id, name, usertype, status, krb_principal)\n        VALUES (9, \'builder1.domain.local\', 1, 0, NULL)\''>

Aha, time for some db cleaning. After cleaning the koji postgres database, I re-issue the “koji add-host” command

1
2
3
4
5
6
7
8

[kojiadmin@hub ~]$ koji add-host builder1.domain.local x86_64
builder1.domain.local added: id 1

[root@builder1 koji]# /etc/init.d/kojid start
Starting kojid:

[root@builder1 koji]# ps aux |grep kojid
root     17274  1.3  0.0  ?        S    23:40   0:00 /usr/bin/python /usr/sbin/kojid --force-lock --verbose

Yeah :-)! Problem fixed.

Much of what looks like rudeness in hacker circles is not intended to give offense. Rather, it’s the product of the direct, cut-through-the-bullshit communications style that is natural to people who are more concerned about solving problems than making others feel warm and fuzzy.

Eric S. Raymond