Archive for May, 2008

Aligning data from separate files using Haskell

Friday, May 30th, 2008

If you need to align the data from multiple files fast, Haskell is the way to go. For example, given a number of files, with an equal number of lines, each containing a number. How can we easily create a single file where each line contains items from each of the original files, separated by a separator of your choice?

One way to do it is like this.

  1. module Main() where
  3. import Control.Monad(mapM)
  4. import Data.List(transpose, intersperse)
  5. import System.Environment(getArgs)
  6. import System.IO
  8. main = do
  9. header:lookups:files <- getArgs
  10. handles <- mapM (\x -> openFile x ReadMode) files
  11. contents <- mapM hGetContents handles
  12. let output = map (concat . (\x -> intersperse “:” (lookups:x))) $ transpose $ map lines contents
  13. putStrLn header
  14. mapM_ putStrLn output

First of all, I think it is good practice to only import the things you need. Hence the e.g., import Control.Monad(mapM). Yet, I can’t seem to import IOMode from System.IO so there I imported the lot.
Second, it is paramount that each line inside a do statement has the same type, namely IO () in this case. This means we use a mapM_ in the last statement (mapM_ :: (Monad m) => (a -> m b) -> [a] -> m (), where m becomes IO).

Essentially, we handle all files simultaneously, by mapping functions manipulating them into the IO monad using mapM (the type is mapM :: (Monad m) => (a -> m b) -> [a] -> m [b], where once again m becomes IO as we’re executing actions in main :: IO ()). For example, we read the contents of each file in a lazy manner using hGetContents, which results in something that has the type IO [String]. Since we assigned this to the contents name, using <-, contents :: [String]. So, we have a list of Strings, representing the content of each file. Using pure functions, we get the data in the shape we like: we split the contents of each file with lines, and transpose the result. Then we can inject the separator using intersperse and we concatenate the result. Finally, we need to show the result. We put everything to stdout, using putStrLn :: String -> IO (). Because we like a header in our new file, we print it out first. Then we print each line of the new file.

Admittedly, I used to have a hard time grokking this, but since I looked at the Write yourself a Scheme in 48 hours things have picked up.

Tags: , , ,
Posted in Uncategorized | 3 Comments »

Using performance counters with multi-threaded applications

Friday, May 23rd, 2008

Since a few years, there is quite good support for using performance counters on Linux machines. Examples are OProfile (which has been included in the kernel since 2.6, I think), Perfctr, and Perfmon (not to be confused with the other Perfmon, which is a SNMP based performance monitoring tool). I think Perfmon is destined to make it to the kernel source tree as well, or so I’ve heard. Yet, I have been using Perfctr since I started my research, so this post is only about that tool.

There has been talk on the Perfctr mailing list (which gets hopelessly spammed these days) for including support for multi-threaded processes, but thus far I’ve seen nothing that does what I want. So, without further ado, here’s how to patch your kernel to support multi-threaded applications.

I assume you know how to install the basic Perfctr driver, and compile your kernel to add support for it. If possible, compile it as a module, as this is easiest if you need to change things (unless you also change stuff in the kernel header files, in which case you probably want to recompile the complete kernel). Let’s further assume your kernel source lives in /usr/src/linux, further referred to as toplevel. I’ll also assume we’re building the Perfctr module here.

The first thing that needs to be done is make sure that child processes set up their kernel data structures such that performance counter data can be stored at context switch (you want to use virtual counters, i.e., per-process counters). Therefore you need to add a function that does exactly this. We’ll call it __vperfctr_set_child_perfctr(struct task_struct*, struct task_struct*). You also want to be able to set up and empty vperfctr structure, by simply allocating space for it. So, add their existance to your toplevel/include/linux/perfctr.h file (which should be there if you patched the kernel and copied the relevant files when installing Perfctr), which should then read:

  1. #ifdef CONFIG_PERFCTR_MODULE
  2. extern struct vperfctr_stub {
  3. struct module *owner;
  4. void (*exit)(struct vperfctr*);
  5. void (*suspend)(struct vperfctr*);
  6. void (*resume)(struct vperfctr*);
  7. void (*sample)(struct vperfctr*);
  8. struct vperfctr* (*get_empty)(void);
  9. void (*set_child_perfctr) (struct task_struct*, struct task_struct*);
  10. #ifdef CONFIG_PERFCTR_CPUS_FORBIDDEN_MASK
  11. void (*set_cpus_allowed)(struct task_struct*, struct vperfctr*, cpumask_t);
  12. #endif
  13. } vperfctr_stub;
  15. extern void _vperfctr_exit(struct vperfctr*);
  16. #define _vperfctr_suspend(x) vperfctr_stub.suspend((x))
  17. #define _vperfctr_resume(x) vperfctr_stub.resume((x))
  18. #define _vperfctr_sample(x) vperfctr_stub.sample((x))
  19. #define _vperfctr_get_empty() vperfctr_stub.get_empty()
  20. #define _vperfctr_set_child_perfctr(x,y) vperfctr_stub.set_child_perfctr((x),(y))
  21. #define _vperfctr_set_cpus_allowed(x,y,z) (*vperfctr_stub.set_cpus_allowed)((x),(y),(z))
  22. #else /* !CONFIG_PERFCTR_MODULE */
  23. #define _vperfctr_exit(x) __vperfctr_exit((x))
  24. #define _vperfctr_suspend(x) __vperfctr_suspend((x))
  25. #define _vperfctr_resume(x) __vperfctr_resume((x))
  26. #define _vperfctr_sample(x) __vperfctr_sample((x))
  27. #define _vperfctr_get_empty() __vperfctr_get_empty()
  28. #define _vperfctr_set_child_perfctr(x,y) __vperfctr_set_child_perfctr((x),(y))
  29. #define _vperfctr_set_cpus_allowed(x,y,z) __vperfctr_set_cpus_allowed((x),(y),(z))
  30. #endif /* CONFIG_PERFCTR_MODULE */

In the same file you should add some code to the perfctr_copy_task(struct task_struct *, struct pt_regs *) function. Otherwise it only contains a comment stating that nothing should be done until inheritance is implemented and sets the vperfctr structure to NULL. The code for that function should become the following:

  1. static inline void perfctr_copy_task(struct task_struct *child, struct pt_regs *regs) {
  3. if(current->thread.perfctr != NULL) {
  4. child->thread.perfctr = _vperfctr_get_empty();
  5. if(!child->thread.perfctr) {
  6. printk(“PERFCTR::error activating child perfctr\n”);
  7. }
  8. else {
  9. _vperfctr_set_child_perfctr(current, child);
  10. }
  11. }
  12. else {
  13. child->thread.perfctr = NULL;
  14. }
  16. }

The above will get a new structure set up (through __vperfctr_get_empty) and copy the existing settings (i.e., for the control registers etc.) to that structure (through __vperfctr_set_child_perfctr). Before we can use these functions, we need to define them, which is done in toplevel/drivers/perfctr/virtual.c.

  1. struct vperfctr* __vperfctr_get_empty(void) {
  2. return get_empty_vperfctr();
  3. }
  5. void __vperfctr_set_child_perfctr(struct task_struct* parent, struct task_struct* child) {
  7. int err;
  8. struct vperfctr* parent_perfctr = parent->thread.perfctr;
  9. struct vperfctr* child_perfctr = child->thread.perfctr;
  11. if(!child_perfctr) { /* check should have been done before! */
  12. return;
  13. }
  15. child_perfctr->owner = child;
  16. memcpy(&(child_perfctr->cpu_state.control), &(parent_perfctr->cpu_state.control), sizeof(parent_perfctr->cpu_state.control));
  17. child_perfctr->si_signo = parent_perfctr->si_signo;
  19. #ifdef CONFIG_SMP
  20. child_perfctr->sampling_timer = parent_perfctr->sampling_timer;
  21. #endif
  23. err = perfctr_cpu_update_control(&child_perfctr->cpu_state, 0);
  24. if(err < 0) {
  25. printk(“perfctr::error::__vperfctr_set_child cstatus < 0 “);
  26. }
  28. }

I think the Perfctr patch uses p->thread as the first argument, so change this accordingly.

Now, to get the counter values assembled in one central spot, I’m using a second module that accumulates these values. Upon exit, each thread will pass on their values to that module through a hook. The code has protection for usage on multicore processors, through a spin_lock.

Here’s the code you should add to toplevel/drivers/perfctr/virtual.c to be able to access the accumulating module through the hook.

  • void (*__read_counter_update)(int nrctrs, int* events, long long* counters_values) = NULL;
  • int __vperfctr_set_read_counter_hook(void f_address(int, int*, long long*)) {
  • __read_counter_update = f_address;
  • return 0;
  • }
  • EXPORT_SYMBOL(__vperfctr_set_read_counter_hook);
  • int __vperfctr_unset_read_counter_hook(void f_address(int, int*, long long*)) {
  • __read_counter_update = NULL;
  • return 0;
  • }
  • EXPORT_SYMBOL(__vperfctr_unset_read_counter_hook);
  • static void vperfctr_unlink(struct task_struct *owner, struct vperfctr *perfctr) {
  • /* this synchronises with vperfctr_ioctl() */
  • spin_lock(&perfctr->owner_lock);
  • perfctr->owner = NULL;
  • spin_unlock(&perfctr->owner_lock);
  • /* perfctr suspend+detach must be atomic wrt process suspend */
  • /* this also synchronises with perfctr_set_cpus_allowed() */
  • vperfctr_task_lock(owner);
  • if( IS_RUNNING(perfctr) &&owner == current )
  • vperfctr_suspend(perfctr);
  • owner->thread.perfctr = NULL;
  • vperfctr_task_unlock(owner);
  • if(__read_counter_update) {
  • int nractrs = perfctr_cstatus_nractrs(perfctr->cpu_state.cstatus);
  • long long counters [nractrs+1];
  • int events[nractrs+1];
  • int i = 0;
  • for(i = 0; i < nractrs; i++) {
  • events[i] = perfctr->cpu_state.control.evntsel[i];
  • counters[i] = perfctr->cpu_state.pmc[i].sum;
  • }
  • events[nractrs] = -1;
  • counters[nractrs] = perfctr->cpu_state.tsc_sum;
  • __read_counter_update(nractrs, events, counters);
  • }
  • perfctr->cpu_state.cstatus = 0;
  • vperfctr_clear_iresume_cstatus(perfctr);
  • put_vperfctr(perfctr);
  • }

    • The final piece then is the read_counter module where the data is accumulated.

    1. #include >linux/version.h<
    2. #include >linux/vermagic.h<
    3. #include >linux/init.h<
    4. #include >linux/module.h<
    5. #include >linux/kernel.h<
    6. #include >linux/fs.h<
    7. #include >linux/major.h<
    8. #include >linux/errno.h<
    9. #include >asm/uaccess.h<
    10. #include >asm/io.h<
    11. #include >linux/spinlock.h<
    13. MODULE_INFO(vermagic, VERMAGIC_STRING);
    15. #define READ_COUNTERS_DEV 120 /* major number */
    17. #undef unix
    18. struct module __this_module
    19. __attribute__((section(“.gnu.linkonce.this_module”))) = {
    20. .name = __stringify(read_counters),
    21. .init = init_module,
    22. #ifdef CONFIG_MODULE_UNLOAD
    23. .exit = cleanup_module,
    24. #endif
    27. struct counter_info_s {
    28. long long ctrs[9];
    29. int nractrs;
    30. int events[9];
    31. spinlock_t lock;
    34. static struct counter_info_s counters;
    37. void __read_counters_update(int nractrs, int* events, long long* cntrs) {
    39. int i = 0;
    40. spin_lock(&counters.lock);
    41. counters.nractrs = nractrs;
    42. for(i = 0; i < nractrs; ++i) {
    43. counters.ctrs[i] += cntrs[i];
    44. }
    45. spin_unlock(&counters.lock);
    46. }
    49. static int read_counters_open(struct inode* inode, struct file* file) {
    50. printk(“read_counters OPEN\n”);
    51. return 0;
    52. }
    55. static int read_counters_close(struct file* file) {
    56. printk(“read_counters CLOSE\n”);
    57. return 0;
    58. }
    61. static ssize_t read_counters_read(struct file* file, char* buf, size_t count, loff_t *ppos) {
    62. int i = 0;
    63. int res = 0;
    65. res = copy_to_user((void*) buf, (void*) &counters, count);
    66. if(!res) {
    67. /* we reset the counters values at this point */
    68. for(i = 0; i <= counters.nractrs; ++i) {
    69. counters.ctrs[i] = 0;
    70. }
    71. return 0;
    72. }
    74. return -EFAULT;
    75. }
    77. static ssize_t read_counters_write(struct file* file, const char* buf, size_t count, loff_t* ppos) {
    78. return 0;
    79. }
    82. static int read_counters_ioctl(struct inode *inode, struct file *file, unsigned int cmd, unsigned long arg) {
    84. int i;
    85. int res;
    87. /* we have the following legal actions that can be asked
    88. * read: reads the counters
    89. * reset: sets the captured values to zero
    90. *
    91. * cmd is encoded to contain both the desired action (first byte)
    92. * as well as the length of the buffer (last 3 bytes)
    93. */
    95. int action = cmd & 0xff0000;
    96. int count = cmd & 0x0000ff;
    98. switch(action) {
    99. case 0: /* reset */
    100. spin_lock(&counters.lock);
    101. for(i = 0; i <= counters.nractrs; i++) {
    102. counters.ctrs[i] = 0;
    103. counters.events[i] = 0;
    104. }
    105. spin_unlock(&counters.lock);
    106. break;
    107. case 1: /* read */
    108. spin_lock(&counters.lock);
    109. {
    110. char tmp [(counters.nractrs+1)*sizeof(long long)+sizeof(int)];
    111. long long*tmp_counters = (long long*) (tmp+sizeof(int));
    113. *(int*)tmp = counters.nractrs;
    114. for(i = 0; i <= counters.nractrs; ++i) {
    115. *(tmp_counters+i) = counters.ctrs[i];
    116. }
    118. if(count < (counters.nractrs+1)*sizeof(long long)+sizeof(int)) {
    119. res = -EFAULT;
    120. } else {
    121. /*
    122. * we expect arg to contain the address of a
    123. * structure where the counter values can be dropped
      >li class=”indent5″> */

    124. res = (copy_to_user((void*) arg, tmp, (counters.nractrs+1)*sizeof(long long)+sizeof(int)) ? -EFAULT : 0);
    125. }
    126. }
    127. spin_unlock(&counters.lock);
    128. return res;
    129. break;
    130. }
    131. return -1;
    132. }
    134. static struct file_operations read_counters_fops = {
    135. .read = read_counters_read, /* read */
    136. .write = read_counters_write, /* write */
    137. .ioctl = read_counters_ioctl, /* ioctl */
    138. .open = read_counters_open, /* open */
    139. .flush = read_counters_close, /* close */
    140. };
    142. extern int __vperfctr_set_read_counter_hook(void (*f)(int, int*, long long*));
    143. extern int __vperfctr_unset_read_counter_hook(void);
    145. int init_module(void) {
    147. int i = 0;
    149. /* find a symbol called __vperfctr_set_read_counter_hook */
    150. /* if it doesn’t exist, let insmod handle it! :-) */
    152. __vperfctr_set_read_counter_hook(__read_counters_update);
    154. for(i =0; i < 9; ++i) {
    155. counters.ctrs[i] = 0LL;
    156. counters.events[i] = 0;
    157. }
    159. if(register_chrdev(READ_COUNTERS_DEV, “read_counters”, &read_counters_fops) == -EBUSY) {
    160. printk(“READ_COUNTERS device: unable to connect to major number %d\n”, READ_COUNTERS_DEV);
    161. return -EIO;
    162. }
    163. else {
    164. printk(“READ_COUNTERS device installed.\n”);
    165. }
    166. return 0;
    167. }
    169. void cleanup_module(void) {
    170. __vperfctr_unset_read_counter_hook();
    171. if(unregister_chrdev(READ_COUNTERS_DEV, “read_counters”)) {
    172. printk(“READ_COUNTERS device: unable to release device %d\n”, READ_COUNTERS_DEV);
    173. }
    174. else {
    175. printk(“READ_COUNTERS device driver removed\n”);
    176. }
    177. }
    179. MODULE_LICENSE(“GPL”);

    If you wish to read the data, you must create the device /dev/read_counters with major number 120 and minor number 0. Code that does the reading for you might look like this:

    1. #include <sys/types.h>
    2. #include <sys/stat.h>
    3. #include <fcntl.h>
    4. #include <linux/spinlock.h>
    6. struct counter_info_s {
    7. long long ctrs[9];
    8. int nractrs;
    9. int events[9];
    10. spinlock_t lock;
    11. };
    13. struct counter_info_s counters;
    15. int main() {
    17. int file = open(“/dev/read_counters”, O_RDONLY);
    19. if(file < 0) {
    20. perror(“open”);
    21. exit(-1);
    22. }
    24. if(read(file, (void*) &counters, sizeof(struct counter_info_s), 0)) {
    25. perror(“oops. read error.”);
    26. exit(-1);
    27. }
    28. else {
    29. int i = 0;
    30. printf(“read succesfull\n”);
    31. printf(“counters.nractrs = %d\n”, counters.nractrs);
    33. for(i = 0; i < counters.nractrs; ++i) {
    34. printf(“counters.ctrs[%d] = %lld\n”, i, counters.ctrs[i]);
    35. }
    36. exit(0);
    37. }
    38. }

    Tags: , , ,
    Posted in Uncategorized | 1 Comment »

    NMBS delays

    Wednesday, May 14th, 2008

    Two MTI students made a website where people can register the delays they incurred when traveling on the Belgian railroads. For now the website resides on the ELIS servers, and can be reached at http://trappist.elis.ugent.be/~kmillet/. The idea is that the commuters drive the content which should result in an accurate image of the actual delays, rather than the statistics the NMBS gives, as they tend to drop delays smaller than five minutes and prefer to give a more optimistic picture in general. So if you are a commuter, and you use the railroad in Belgium, register and start logging your delays. Spread the word.

    Tags: , , ,
    Posted in Uncategorized | No Comments »

    Protection FAIL

    Tuesday, May 13th, 2008

    Oh joy. After installing a bunch of sun protection screens on the building windows, they decided to turn the power breaker off. So, during what is probably going to be one of the warmer weeks this year, the entire installation is quite useless. So much for good planning.

    Tags: , , ,
    Posted in Uncategorized | 3 Comments »

    The Architect

    Friday, May 9th, 2008

    We have an appointment. With the architect. Next Thursday.

    Let’s hope he has a plan, an affordable one, and one we like on top of that.

    Tags: ,
    Posted in Uncategorized | 3 Comments »

    Only

    Friday, May 9th, 2008

    There’s a cool video clip of NIN’s song Only on the NIN website. Go check it out. It’s not new, but I had not seen it before.

    Tags: , ,
    Posted in Uncategorized | 1 Comment »

    Airport Express

    Friday, May 9th, 2008

    I’ve traded my old amplifier for an Airport Express with Kenneth. Yesterday he also provided me with a power plug, because the Airport comes from the USA, and thus came with the wrong power plug. And I cannot seem to locate mine that came with my PowerBook, nor the one that came with Veerle’s MacBook. Sadly, I seem to misplace a lot of stuff lately ;-)

    Yet, the device works like a charm. I do think I am broadcasting through my Airport Base Star, instead of directly to the Express, as the former seems to be running pretty hot. Still, finally I can let the neighbours enjoy my iTunes library. I’d recommend it to everybody.

    Tags: , ,
    Posted in Uncategorized | 1 Comment »

    Python wrapper for Mollom

    Thursday, May 8th, 2008

    With the release of the Mollom API, I have cleaned up and documented my Python wrapper for the API.

    You can get the code from the darcs repository at http://itkovian.net/darcs/python_mollom. Alternatively, a packed tarball is also available.

    For the moment, the repository contains two files Mollom.py and HTTPTransport.py. The former contains the MollomAPI and MollomFault classes. The latter contains a derived class to deal with HTTP transport in the XML PRC library, as the default Python code does not seem to do things correctly. To get the response from the Mollom service as a Python dictionary, you need to either use the provided HTTPTransport class or provide your own implementation

    To deal with caching and using session IDs a MollomBase class is present, which can be overridden to allow a user defined caching mechanism for the server list to be used. This class is still under heavy development, so it is prone to (frequent) changes.

    MollomAPI offers the following methods:

    • getServerList
    • checkContent
    • sendFeedback
    • getImageCaptcha
    • getAudioCaptcha
    • checkCaptcha
    • getStatistics
    • verifyKey

    I plan to see if I can get this into Django as well as a contributed app that can be included in a Django project.

    Update (2008/09/18) I have incorporated the changes made to the API document on 2008/09/10. The version of the tarball has been bumped to 0.2. Additionally some bugs were fixed, so you might want to update to this version rather than sticking with the old one.

    Update (2010/02/08) I have moved the code to a new repository at GitHub. Get the library using git clone git://github.com/itkovian/PyMollom.git. For now, I do plan on keeping the darcs repo hosted at my website and the github repo in sync, so you can pull from either.

    Tags: , ,
    Posted in Uncategorized | 6 Comments »

    PhD obtained

    Thursday, May 1st, 2008

    On April 300, 2008 I successfully held my public PhD defense. You can find the PDF of my dissertation here. I have also put the presentation slides online in PDF format.

    This is probably the most important slide I showed:

    Honesty

    Tags: , ,
    Posted in Uncategorized | 4 Comments »