Monthly Archives: June 2016

shortest path

https://www.careercup.com/question?id=5722862468988928

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <time.h>

enum {
	G,
	O,
	W,
};

struct position {
	int x, y;
	int type;
	int distance;
	void *visited;
};

#define QUEUE_SIZE 100
#define ROW 5
#define COL 4

struct position matrix[ROW][COL];

struct queue {
	struct position *entries[QUEUE_SIZE];
	int head, tail;
};

void init_queue(struct queue *q)
{
	q->head = q->tail = 0;
}

int empty(struct queue *q)
{
	return (q->head == q->tail);
}

void enqueue(struct queue *q, struct position *p)
{
	int tail = q->tail;

	q->entries[tail] = p;
	q->tail = (q->tail + 1) % QUEUE_SIZE;
}

struct position *dequeue(struct queue *q)
{
	struct position *p;

	p = q->entries[q->head];
	q->head = (q->head + 1) % QUEUE_SIZE;

	return p;
}

struct position *up(struct position *p)
{
	if (p->x == 0)
		return NULL;

	return &matrix[p->x - 1][p->y];
}

struct position *down(struct position *p)
{
	if (p->x == ROW - 1)
		return NULL;

	return &matrix[p->x + 1][p->y];
}

struct position *left(struct position *p)
{
	if (p->y == 0)
		return NULL;

	return &matrix[p->x][p->y - 1];
}

struct position *right(struct position *p)
{
	if (p->y == COL - 1)
		return NULL;

	return &matrix[p->x][p->y + 1];
}

void check_direction(struct position *p, struct position *guard, struct queue *q)
{
	int distance = p->distance + 1;

	if (!guard || guard->type != O || guard->visited == p)
		return;

	if (distance < guard->distance) {
		guard->distance = distance;
		enqueue(q, guard);
	}

	guard->visited = p;
}

void one_guard_bfs(struct position *guard)
{
	struct queue *q, _q;

	q = &_q;
	init_queue(q);

	guard->distance = 0;
	guard->visited = guard;
	enqueue(q, guard);

	while (!empty(q)) {
		guard = dequeue(q);	

		check_direction(guard, up(guard), q);
		check_direction(guard, down(guard), q);
		check_direction(guard, left(guard), q);
		check_direction(guard, right(guard), q);
	}
}

void all_guards_bfs(struct position p[ROW][COL], int m, int n)
{
	int i, j;	

	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			if (p[i][j].type == G)
				one_guard_bfs(&p[i][j]);
}

int main()
{
	int type[ROW][COL] = {
		{O, W, G, W},
		{O, G, O, G},
		{O, G, O, W},
		{W, O, O, O},
		{G, O, O, O},
	};

	int i, j;

	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			matrix[i][j].type = type[i][j];
			matrix[i][j].x = i;
			matrix[i][j].y = j;
			matrix[i][j].distance = 9999;
		}
	}

	all_guards_bfs(matrix, ROW, COL);

	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			if (matrix[i][j].type == O)
				printf("%d, %d: %d\n", i, j, matrix[i][j].distance);
		}
	}

	return 0;
}

 

social network components

http://www.slideshare.net/Mugar1988/facebook-architecture-presentation-scalability-challenge

http://royal.pingdom.com/2010/06/18/the-software-behind-facebook/

caching: https://memcached.org/

photo storage: https://github.com/chrislusf/seaweedfs

graph database: http://neo4j.com/

friend recommendation(machine learning): http://mahout.apache.org/ 

data storage: http://cassandra.apache.org/

social network engine: https://elgg.org/

killall -9 mytest

[ 59.004047] CPU: 1 PID: 1432 Comm: mytest Not tainted 4.7.0-rc2+ #250
[ 59.004059] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.8.2-0-g33fbe13 by qemu-project.org 04/01/2014
[ 59.004061] 0000000000000000 ffff880137547cf8 ffffffff8133018a ffff88007f049e48
[ 59.004063] ffff88007f049be0 ffff880137547d60 ffffffff8106f865 0000000001bf0005
[ 59.004064] 0000000137547d60 000000053fffae00 ffff88007f049f00 ffff880137547d28
[ 59.004066] Call Trace:
[ 59.004071] [<ffffffff8133018a>] dump_stack+0x63/0x89
[ 59.004074] [<ffffffff8106f865>] do_exit+0xb05/0xb20
[ 59.004076] [<ffffffff8106f8fa>] do_group_exit+0x3a/0xa0
[ 59.004078] [<ffffffff81079a1d>] get_signal+0x1ed/0x560
[ 59.004080] [<ffffffff81025363>] do_signal+0x23/0x750
[ 59.004083] [<ffffffff81095ef0>] ? pick_next_entity+0xa0/0x150
[ 59.004085] [<ffffffff810246ba>] ? __switch_to+0x20a/0x590
[ 59.004087] [<ffffffff8108ce53>] ? finish_task_switch+0x73/0x1f0
[ 59.004090] [<ffffffff816eed5e>] ? __schedule+0x1de/0x590
[ 59.004093] [<ffffffff81059bd8>] ? __do_page_fault+0x1c8/0x4e0
[ 59.004094] [<ffffffff810674a0>] exit_to_usermode_loop+0x47/0x90
[ 59.004097] [<ffffffff81003386>] prepare_exit_to_usermode+0x26/0x30
[ 59.004098] [<ffffffff816f3325>] retint_user+0x8/0x13

[ 26.392961] CPU: 0 PID: 1449 Comm: bash Not tainted 4.7.0-rc2+ #251
[ 26.392962] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.8.2-0-g33fbe13 by qemu-project.org 04/01/2014
[ 26.392963] 0000000000000000 ffff88007f5d7da8 ffffffff813301aa 00007fffffffeffd
[ 26.392964] ffff88013a118c00 ffff88007f5d7e00 ffffffff8106de26 00000000000005b6
[ 26.392965] ffff88007f5d7e00 ffffffff8109532c 000000000000059d 00007fffffffeffd
[ 26.392967] Call Trace:
[ 26.392969] [<ffffffff813301aa>] dump_stack+0x63/0x89
[ 26.392971] [<ffffffff8106de26>] release_task+0x486/0x4a0
[ 26.392973] [<ffffffff8109532c>] ? thread_group_cputime_adjusted+0x3c/0x50
[ 26.392975] [<ffffffff8106e429>] wait_consider_task+0x5e9/0xb00
[ 26.392976] [<ffffffff8106ea26>] do_wait+0xe6/0x1f0
[ 26.392978] [<ffffffff8106fb70>] SyS_wait4+0x60/0xc0
[ 26.392979] [<ffffffff8106d910>] ? task_stopped_code+0x50/0x50
[ 26.392982] [<ffffffff816f29f6>] entry_SYSCALL_64_fastpath+0x1e/0xa

NVMe driver poll mode

Note that, current Linux kernel’s blk_poll doesn’t support async IO.
So for fio, you can’t use libaio engine to test poll mode.
I use psync in blow tests.

You also need to revert below commit and rebuild kernel to test it.
Otherwise, you’ll need to modify fio code.

mlin@ssi:~/linux$ git show c43c83a294e8dc25072ca9e6fca4cdbc5564f3d4
commit c43c83a294e8dc25072ca9e6fca4cdbc5564f3d4
Author: Christoph Hellwig <hch@lst.de>
Date: Thu Mar 3 16:04:02 2016 +0100

direct-io: only use block polling if explicitly requested

Signed-off-by: Christoph Hellwig <hch@lst.de>
Reviewed-by: Stephen Bates <stephen.bates@pmcs.com>
Tested-by: Stephen Bates <stephen.bates@pmcs.com>
Acked-by: Jeff Moyer <jmoyer@redhat.com>
Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>

===================
My test results:

poll mode enabled:
lat (usec): min=16, max=85, avg=19.65, stdev= 1.11

disabled:
lat (usec): min=18, max=67, avg=22.21, stdev= 1.08

root@target:~# grep . /sys/block/nvme0n1/mq/*/io_poll
/sys/block/nvme0n1/mq/0/io_poll:invoked=382092120, success=546330
/sys/block/nvme0n1/mq/1/io_poll:invoked=14736531, success=30177
/sys/block/nvme0n1/mq/2/io_poll:invoked=256434558, success=503203
/sys/block/nvme0n1/mq/3/io_poll:invoked=318064773, success=508663
/sys/block/nvme0n1/mq/4/io_poll:invoked=1694677560, success=1129213
/sys/block/nvme0n1/mq/5/io_poll:invoked=164542953, success=275110
/sys/block/nvme0n1/mq/6/io_poll:invoked=128142476, success=240194
/sys/block/nvme0n1/mq/7/io_poll:invoked=0, success=0

root@target:~# cat t.job
[global]
ioengine=psync
direct=1
runtime=10
time_based
norandommap
group_reporting

[job1]
filename=/dev/nvme0n1
rw=randread
bs=4k
iodepth=1
numjobs=1
root@target:~# echo 1 > /sys/block/nvme0n1/queue/io_poll
root@target:~# fio t.job
job1: (g=0): rw=randread, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.8-26-g603e
Starting 1 process
Jobs: 1 (f=1): [r(1)] [100.0% done] [194.8MB/0KB/0KB /s] [49.9K/0/0 iops] [eta 00m:00s]
job1: (groupid=0, jobs=1): err= 0: pid=2130: Wed Jun 8 14:34:02 2016
read : io=1943.1MB, bw=199063KB/s, iops=49765, runt= 10000msec
clat (usec): min=16, max=84, avg=19.59, stdev= 1.11
lat (usec): min=16, max=85, avg=19.65, stdev= 1.11
clat percentiles (usec):
| 1.00th=[ 18], 5.00th=[ 18], 10.00th=[ 18], 20.00th=[ 19],
| 30.00th=[ 19], 40.00th=[ 19], 50.00th=[ 20], 60.00th=[ 20],
| 70.00th=[ 20], 80.00th=[ 20], 90.00th=[ 21], 95.00th=[ 21],
| 99.00th=[ 22], 99.50th=[ 23], 99.90th=[ 24], 99.95th=[ 26],
| 99.99th=[ 31]
bw (KB /s): min=191520, max=200360, per=99.99%, avg=199034.95, stdev=1854.33
lat (usec) : 20=48.20%, 50=51.80%, 100=0.01%
cpu : usr=3.36%, sys=96.56%, ctx=33, majf=0, minf=10
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued : total=r=497658/w=0/d=0, short=r=0/w=0/d=0, drop=r=0/w=0/d=0
latency : target=0, window=0, percentile=100.00%, depth=1

Run status group 0 (all jobs):
READ: io=1943.1MB, aggrb=199063KB/s, minb=199063KB/s, maxb=199063KB/s, mint=10000msec, maxt=10000msec

Disk stats (read/write):
nvme0n1: ios=492410/0, merge=0/0, ticks=8744/0, in_queue=8708, util=87.18%
root@target:~# echo 0 > /sys/block/nvme0n1/queue/io_poll
root@target:~# fio t.job
job1: (g=0): rw=randread, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.8-26-g603e
Starting 1 process
Jobs: 1 (f=1): [r(1)] [100.0% done] [171.6MB/0KB/0KB /s] [43.1K/0/0 iops] [eta 00m:00s]
job1: (groupid=0, jobs=1): err= 0: pid=2141: Wed Jun 8 14:34:44 2016
read : io=1709.1MB, bw=175078KB/s, iops=43769, runt= 10001msec
clat (usec): min=18, max=66, avg=22.12, stdev= 1.07
lat (usec): min=18, max=67, avg=22.21, stdev= 1.08
clat percentiles (usec):
| 1.00th=[ 20], 5.00th=[ 21], 10.00th=[ 21], 20.00th=[ 21],
| 30.00th=[ 22], 40.00th=[ 22], 50.00th=[ 22], 60.00th=[ 22],
| 70.00th=[ 23], 80.00th=[ 23], 90.00th=[ 23], 95.00th=[ 24],
| 99.00th=[ 25], 99.50th=[ 25], 99.90th=[ 29], 99.95th=[ 30],
| 99.99th=[ 44]
bw (KB /s): min=169808, max=175784, per=99.99%, avg=175066.11, stdev=1297.33
lat (usec) : 20=0.18%, 50=99.81%, 100=0.01%
cpu : usr=10.24%, sys=7.48%, ctx=437745, majf=0, minf=11
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued : total=r=437740/w=0/d=0, short=r=0/w=0/d=0, drop=r=0/w=0/d=0
latency : target=0, window=0, percentile=100.00%, depth=1

Run status group 0 (all jobs):
READ: io=1709.1MB, aggrb=175078KB/s, minb=175078KB/s, maxb=175078KB/s, mint=10001msec, maxt=10001msec

Disk stats (read/write):
nvme0n1: ios=433278/0, merge=0/0, ticks=8172/0, in_queu