changelog shortlog tags branches changeset files revisions annotate raw help

Mercurial > hg > plan9front / sys/src/games/packet.c

changeset 4350: 1f9d7811d546
parent: 60035b7186cb
author: cinap_lenrek@felloff.net
date: Mon, 16 Mar 2015 05:46:08 +0100
permissions: -rw-r--r--
description: kernel: get rid of auxpage() and preserve cache index bits in Page.va in mount cache

the mount cache uses Page.va to store cached range offset and
limit, but mips kernel uses cache index bits from Page.va to
maintain page coloring. Page.va was not initialized by auxpage().

this change removes auxpage() which was primarily used only
by the mount cache and use newpage() with cache file offset
page as va so we will get a page of the right color.

mount cache keeps the index bits intact by only using the top
and buttom PGSHIFT bits of Page.va for the range offset/limit.
1 #include <u.h>
2 #include <libc.h>
3 #include <thread.h>
4 #include <draw.h>
5 #include <mouse.h>
6 
7 #define minx -1.0
8 #define maxx 1.0
9 #define miny -1.0
10 #define maxy 1.0
11 
12 double speedOff = 0.001;
13 double decay = 0.99;
14 double speedBonus = 0.001;
15 int regenRate = 5;
16 double thickFactor = 0.01;
17 double dispThresh = 0.001;
18 #define ncolours 200
19 int nnode = 40;
20 
21 typedef struct Pos Pos;
22 typedef struct List List;
23 typedef struct Node Node;
24 typedef struct Pack Pack;
25 
26 struct Pos
27 {
28  double x, y;
29 };
30 
31 struct List
32 {
33  void *next, *prev;
34 };
35 
36 struct Node
37 {
38  Pos;
39  int die, ref, targref;
40 };
41 
42 struct Pack
43 {
44  List;
45  Pos;
46  int targ, p, q;
47  double λ, v;
48  Image *c;
49 };
50 
51 Node *nodes;
52 Pack plist;
53 Mousectl *mctl;
54 double *dist, *path, *speed, *speedn;
55 int *nextn;
56 Image *col[ncolours];
57 Image *grey;
58 
59 void *
60 emallocz(int size)
61 {
62  void *v;
63 
64  v = mallocz(size, 1);
65  if(v == nil)
66  sysfatal("malloc: %r");
67  setmalloctag(v, getcallerpc(&size));
68  return v;
69 }
70 
71 Point
72 convert(Pos* p)
73 {
74  return (Point){
75  screen->r.min.x + (screen->r.max.x - screen->r.min.x) *
76  ((p->x - minx) / (maxx - minx)),
77  screen->r.min.y + (screen->r.max.y - screen->r.min.y) *
78  ((p->y - minx) / (maxx - minx))};
79 }
80 
81 Pos
82 deconvert(Point p)
83 {
84  return (Pos){
85  minx + (maxx - minx) *
86  ((double)(p.x - screen->r.min.x) / (screen->r.max.x - screen->r.min.x)),
87  miny + (maxy - miny) *
88  ((double)(p.y - screen->r.min.y) / (screen->r.max.y - screen->r.min.y))};
89 }
90 
91 void
92 rect(Pos *p, int size, Image *col)
93 {
94  Point poi;
95  Rectangle r;
96 
97  poi = convert(p);
98  r = insetrect(Rpt(poi, poi), -size);
99  draw(screen, r, col, nil, ZP);
100 }
101 
102 List *
103 add(List *head, List *obj)
104 {
105  obj->prev = head->prev;
106  obj->next = head;
107  ((List*)head->prev)->next = obj;
108  head->prev = obj;
109  return obj;
110 }
111 
112 List *
113 unlink(List *obj)
114 {
115  ((List*)obj->prev)->next = obj->next;
116  ((List*)obj->next)->prev = obj->prev;
117  return obj;
118 }
119 
120 void
121 calcdist(void)
122 {
123  int i, j;
124  double dx, dy;
125 
126  dist = realloc(dist, sizeof(*dist) * nnode * nnode);
127  path = realloc(path, sizeof(*path) * nnode * nnode);
128  nextn = realloc(nextn, sizeof(*nextn) * nnode * nnode);
129  for(i = 0; i < nnode; i++)
130  for(j = 0; j < nnode; j++){
131  if(nodes[j].die == 2){
132  dist[i * nnode + j] = Inf(1);
133  continue;
134  }
135  dx = nodes[i].x - nodes[j].x;
136  dy = nodes[i].y - nodes[j].y;
137  dist[i * nnode + j] = sqrt(dx * dx + dy * dy);
138  }
139 }
140 
141 u32int
142 randomcol(void)
143 {
144  int c[3] = {0, 255, 0};
145  int *j, t;
146 
147  c[2] = rand() % 256;
148  j = c + rand() % 3;
149  t = c[2];
150  c[2] = *j;
151  *j = t;
152  if(rand()%2){
153  t = c[1];
154  c[1] = c[0];
155  c[0] = t;
156  }
157  return (c[0] << 24) | (c[1] << 16) | (c[2] << 8) | 0xFF;
158 }
159 
160 void
161 createstuff(void)
162 {
163  int i;
164  plist.next = &plist;
165  plist.prev = &plist;
166 
167  for(i = 0; i < ncolours; i++)
168  col[i] = allocimage(display, Rect(0, 0, 1, 1), screen->chan, 1, randomcol());
169  grey = allocimage(display, Rect(0, 0, 1, 1), screen->chan, 1, 0x888888FF);
170 
171  nodes = emallocz(sizeof(*nodes) * nnode);
172  for(i = 0; i < nnode; i++){
173  nodes[i].x = frand() * (maxx - minx) + minx;
174  nodes[i].y = frand() * (maxy - miny) + miny;
175  }
176  calcdist();
177  speed = emallocz(sizeof(*speed) * nnode * nnode);
178  speedn = emallocz(sizeof(*speedn) * nnode * nnode);
179 }
180 
181 void
182 resizespeed(int diff)
183 {
184  int nnode1, i, j;
185 
186  nnode1 = nnode - diff;
187  speedn = realloc(speedn, sizeof(*speedn) * nnode * nnode);
188  for(i = 0; i < nnode; i++)
189  for(j = 0; j < nnode; j++)
190  if(i < nnode1 && j < nnode1)
191  speedn[i * nnode + j] = speed[i * nnode1 + j];
192  else
193  speedn[i * nnode + j] = 0;
194  speed = realloc(speed, sizeof(*speedn) * nnode * nnode);
195  memcpy(speed, speedn, sizeof(*speedn) * nnode * nnode);
196 }
197 
198 void
199 createpacket(void)
200 {
201  Pack *p;
202 
203  p = emallocz(sizeof(*p));
204  do{
205  p->q = rand() % nnode;
206  p->targ = rand() % nnode;
207  }while(p->q == p->targ || nodes[p->q].die || nodes[p->targ].die);
208  nodes[p->q].ref++;
209  nodes[p->targ].targref++;
210  p->p = -1;
211  p->Pos = nodes[p->q].Pos;
212  p->c = col[rand() % ncolours];
213  add(&plist, p);
214 }
215 
216 int
217 getpath(int i, int j)
218 {
219  int k;
220 
221  i *= nnode;
222  while((k = nextn[i + j]) != j)
223  j = k;
224  return j;
225 }
226 
227 void
228 floyd(void)
229 {
230  int i, j, k;
231  double a, *b;
232 
233  for(i = 0; i < nnode; i++)
234  for(j = 0; j < nnode; j++){
235  path[i * nnode + j] = dist[i * nnode + j] / (speedOff + speed[i * nnode + j]);
236  nextn[i * nnode + j] = j;
237  }
238  for(k = 0; k < nnode; k++)
239  for(i = 0; i < nnode; i++)
240  for(j = 0; j < nnode; j++){
241  a = path[i * nnode + k] + path[k * nnode + j];
242  b = path + i * nnode + j;
243  if(a < *b){
244  *b = a;
245  nextn[i * nnode + j] = k;
246  }
247  }
248 }
249 
250 void
251 createnode(Pos p)
252 {
253  int i, j;
254 
255  j = nnode;
256  for(i = 0; i < nnode; i++){
257  if(nodes[i].Pos.x == p.x && nodes[i].Pos.y == p.y)
258  return;
259  if(nodes[i].die == 3 && j == nnode)
260  j = i;
261  }
262  if(j == nnode){
263  nodes = realloc(nodes, sizeof(*nodes) * ++nnode);
264  resizespeed(1);
265  }
266  nodes[j].Pos = p;
267  nodes[j].die = 0;
268  nodes[j].ref = 0;
269  nodes[j].targref = 0;
270  calcdist();
271  floyd();
272 }
273 
274 Pack *
275 advancepacket(Pack *p)
276 {
277  Pack *n;
278  Node *np, *nq;
279 
280  if(p->p == -1){
281  p->p = p->q;
282  p->q = getpath(p->q, p->targ);
283  nodes[p->q].ref++;
284  p->λ = 0;
285  p->v = (speedOff + speed[p->p * nnode + p->q]) / dist[p->p * nnode + p->q];
286  }else{
287  p->λ += p->v;
288  if(p->λ >= 1){
289  speedn[p->p * nnode + p->q] += speedBonus;
290  speedn[p->q * nnode + p->p] += speedBonus;
291  nodes[p->p].ref--;
292  p->p = -1;
293  if(p->q == p->targ){
294  n = p->next;
295  nodes[p->q].ref--;
296  nodes[p->q].targref--;
297  free(unlink(p));
298  return n;
299  }
300  p->Pos = nodes[p->q].Pos;
301  return p->next;
302  }
303  }
304  np = nodes + p->p;
305  nq = nodes + p->q;
306  p->x = np->x * (1 - p->λ) + nq->x * p->λ;
307  p->y = np->y * (1 - p->λ) + nq->y * p->λ;
308  return p->next;
309 }
310 
311 long sync;
312 
313 void
314 timing()
315 {
316  for(;;){
317  semrelease(&sync, 1);
318  sleep(25);
319  }
320 }
321 
322 void
323 simstep(void)
324 {
325  static int regen;
326  Pack *p;
327  int i, j;
328 
329  for(p = plist.next; p != &plist; )
330  p = advancepacket(p);
331  for(i = 0; i < nnode; i++){
332  if(nodes[i].die == 1 && nodes[i].targref == 0){
333  nodes[i].die++;
334  calcdist();
335  }
336  if(nodes[i].die == 2 && nodes[i].ref == 0){
337  nodes[i].die++;
338  for(j = 0; j < nnode; j++)
339  speedn[i * nnode + j] = speedn[i + j * nnode] = 0;
340  }
341  }
342  for(i = 0; i < nnode * nnode; i++)
343  speed[i] = speedn[i] *= decay;
344  floyd();
345  if(regen-- == 0){
346  regen = rand() % regenRate;
347  createpacket();
348  createpacket();
349  }
350 }
351 
352 void
353 domouse(void)
354 {
355  static Mouse m;
356  int lastbut;
357  double dx, dy, d;
358  int i;
359  Point poi;
360 
361  if(nbrecv(mctl->resizec, &i) == 1)
362  if(getwindow(display, Refnone) < 0)
363  sysfatal("getwindow: %r");
364  lastbut = m.buttons;
365  nbrecv(mctl->c, &m);
366  if(lastbut & 4 && !(m.buttons & 4))
367  for(i = 0; i < nnode; i++){
368  poi = convert(&nodes[i]);
369  dx = poi.x - m.xy.x;
370  dy = poi.y - m.xy.y;
371  d = sqrt(dx * dx + dy * dy);
372  if(d < 5){
373  nodes[i].die = 1;
374  break;
375  }
376  }
377  if(lastbut & 1 && !(m.buttons & 1))
378  createnode(deconvert(m.xy));
379 }
380 
381 void
382 usage(void)
383 {
384  fprint(2, "USAGE: %s options\n", argv0);
385  fprint(2, " -n number of nodes [40]\n");
386  fprint(2, " -o speed of unused connections [0.001]\n");
387  fprint(2, " -d decay rate [0.99]\n");
388  fprint(2, " -b speed bonus per packet [0.001]\n");
389  fprint(2, " -r packet generation period [5]\n");
390  fprint(2, " -t line thickness factor [0.01]\n");
391  fprint(2, " -T display threshold [0.001]\n");
392  exits("usage");
393 }
394 
395 void
396 threadmain(int argc, char **argv)
397 {
398  Node *n;
399  Pack *p;
400  int i, j;
401 
402  ARGBEGIN{
403  case 'n': nnode = atoi(EARGF(usage())); break;
404  case 'o': speedOff = atof(EARGF(usage())); break;
405  case 'd': decay = atof(EARGF(usage())); break;
406  case 'b': speedBonus = atof(EARGF(usage())); break;
407  case 'r': regenRate = atoi(EARGF(usage())); break;
408  case 't': thickFactor = atof(EARGF(usage())); break;
409  case 'T': dispThresh = atof(EARGF(usage())); break;
410  default: usage();
411  }ARGEND;
412 
413  initdraw(nil, nil, nil);
414  mctl = initmouse(nil, screen);
415  srand(time(0));
416  createstuff();
417  floyd();
418  proccreate(timing, nil, mainstacksize);
419  for(;;){
420  domouse();
421  draw(screen, screen->r, display->white, nil, ZP);
422  for(i = 0; i < nnode; i++)
423  for(j = 0; j < i; j++)
424  if(speed[i * nnode + j] >= dispThresh)
425  line(screen, convert(nodes + i), convert(nodes + j), 0, 0, speed[i * nnode + j] / thickFactor, display->black, ZP);
426  for(n = nodes; n < nodes + nnode; n++)
427  if(!n->die || n->ref)
428  rect(n, 3, n->die ? grey : display->black);
429  for(p = plist.next; p != &plist; p = p->next)
430  rect(p, 2, p->c);
431  flushimage(display, 1);
432  simstep();
433  semacquire(&sync, 1);
434  }
435 }