source: trunk/kernel/arch/tsar/arch-dqdt.c @ 126

Last change on this file since 126 was 1, checked in by alain, 7 years ago

First import

File size: 8.1 KB
Line 
1/*
2 * arch-dqdt.c - build the Distributed Quaternary Decision Tree
3 * (see kern/dqdt.h)
4 *
5 * Copyright (c) 2008,2009,2010,2011,2012 Ghassan Almaless
6 * Copyright (c) 2011,2012 UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-kernel.
9 *
10 * ALMOS-kernel is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-kernel is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <errno.h>
25#include <types.h>
26#include <cpu.h>
27#include <bits.h>
28#include <thread.h>
29#include <system.h>
30#include <kmem.h>
31#include <arch-bib.h>
32#include <boot-info.h>
33#include <cluster.h>
34#include <kdmsg.h>
35#include <dqdt.h>
36
37#if 0
38uint_t arch_dqdt_distance(struct dqdt_cluster_s *c1, struct dqdt_cluster_s *c2, struct dqdt_attr_s *attr)
39{
40        register sint_t x1,y1,x2,y2,d;
41 
42        switch(attr->d_attr)
43        {
44        case DQDT_DIST_DEFAULT:
45                x1 = c1->home->x_coord;
46                y1 = c1->home->y_coord;
47                x2 = c2->home->x_coord;
48                y2 = c2->home->y_coord;
49                d = ABS((x1 - x2)) + ABS((y1 - y2));
50                break;
51
52        case DQDT_DIST_RANDOM:
53                //srand(cpu_time_stamp());
54                d = rand() % 0xFFF;
55                break;
56
57        default:
58                d = 1;
59                break;
60        }
61
62        return d;
63}
64
65static uint_t __cluster_index(uint_t x, uint_t y, uint_t ymax)
66{
67        return x*ymax + y;
68}
69
70error_t arch_dqdt_chip_init(struct dqdt_cluster_s ***chip,
71                            struct cluster_entry_s *clusters_tbl,
72                            uint_t xmax,
73                            uint_t ymax)
74{
75        struct dqdt_cluster_s *ptr;
76        kmem_req_t req;
77        uint_t chip_xmax;
78        uint_t chip_ymax;
79        uint_t x;
80        uint_t y;
81        uint_t cid;
82
83        dqdt_dmsg(1, "%s: real (%d x %d)\n", __FUNCTION__, xmax, ymax);
84
85        req.type  = KMEM_GENERIC;
86        req.size  = sizeof(*ptr);
87        chip_xmax = CONFIG_MAX_CLUSTER_ROOT;
88        chip_ymax = chip_xmax;
89
90        for(x = 0; x < chip_xmax; x++)
91                for(y = 0; y < chip_ymax; y++)
92                        chip[x][y] = NULL;
93
94        req.flags = AF_BOOT | AF_REMOTE | AF_ZERO;
95
96        for(x = 0; x < xmax; x++)
97        {
98                for(y = 0; y < ymax; y++)
99                {
100                        cid = __cluster_index(x, y, ymax);
101     
102                        if(clusters_tbl[cid].cluster == NULL)
103                                continue;
104
105                        req.ptr = clusters_tbl[cid].cluster;
106                        ptr     = kmem_alloc(&req);
107
108                        if(ptr == NULL)
109                                return ENOMEM;
110
111                        ptr->cores_nr            = clusters_tbl[cid].cluster->onln_cpu_nr;
112                        ptr->flags               = DQDT_CLUSTER_UP;
113                        ptr->home                = clusters_tbl[cid].cluster;
114                        ptr->home->levels_tbl[0] = ptr;
115                        ptr->home->x_coord       = x;
116                        ptr->home->y_coord       = y;
117                        ptr->home->z_coord       = 0;
118                        ptr->home->chip_id       = 0;
119                        chip[x][y]               = ptr;
120
121                        dqdt_dmsg(1, "%s: found cid %d, x %d, y %d, ptr %x\n",
122                                  __FUNCTION__,
123                                  cid,
124                                  x,
125                                  y,
126                                  ptr);
127                }
128        }
129
130        req.flags = AF_BOOT | AF_ZERO;
131
132        for(x = 0; x < chip_xmax; x++)
133        {
134                for(y = 0; y < chip_ymax; y++)
135                {
136                        if(chip[x][y] != NULL)
137                                continue;
138     
139                        ptr = kmem_alloc(&req);
140     
141                        if(ptr == NULL)
142                                return ENOMEM;
143
144                        chip[x][y] = ptr;
145                }
146        }
147
148        return 0;
149}
150
151static struct dqdt_cluster_s *** arch_dqdt_alloc_matrix(uint_t xmax, uint_t ymax)
152{
153        uint_t x;
154        kmem_req_t req;
155        struct dqdt_cluster_s ***matrix;
156
157        dqdt_dmsg(1, "%s: %d x %d\n", __FUNCTION__, xmax, ymax);
158 
159        req.type  = KMEM_GENERIC;
160        req.size  = xmax * sizeof(*matrix);
161        req.flags = AF_BOOT;
162 
163        matrix = kmem_alloc(&req);
164
165        if(matrix == NULL)
166                return NULL;
167 
168        for(x = 0; x < xmax; x++)
169        {
170                req.size  = ymax * sizeof(**matrix);
171                matrix[x] = kmem_alloc(&req);
172
173                if(matrix[x] == NULL)
174                        return NULL;
175        }
176 
177        dqdt_dmsg(1, "%s: %d x %d, done\n", __FUNCTION__, xmax, ymax);
178        return matrix;
179}
180
181void arch_dqdt_free_matrix(struct dqdt_cluster_s ***matrix, uint_t xmax, uint_t ymax)
182{
183        uint_t x;
184        kmem_req_t req;
185 
186        req.type = KMEM_GENERIC;
187   
188        for(x = 0; x < xmax; x++)
189        {
190                req.ptr = matrix[x];
191                kmem_free(&req);
192        }
193 
194        req.ptr = matrix;
195        kmem_free(&req);
196}
197
198struct dqdt_cluster_s * arch_dqdt_make_cluster(struct dqdt_cluster_s ***matrix,
199                                               uint_t level,
200                                               uint_t x,
201                                               uint_t y)
202{
203        kmem_req_t req;
204        struct cluster_s *cluster;
205        struct dqdt_cluster_s *ptr;
206        struct dqdt_cluster_s *child0;
207        struct dqdt_cluster_s *child1;
208        struct dqdt_cluster_s *child2;
209        struct dqdt_cluster_s *child3;
210        uint_t clstr_x;
211        uint_t clstr_y;
212        uint_t childs_nr;
213        uint_t cores_nr;
214
215        childs_nr = 0;
216        cores_nr  = 0; 
217        child0    = NULL;
218        child1    = NULL;
219        child2    = NULL;
220        child3    = NULL;
221        cluster   = NULL;
222        clstr_x   = x;
223        clstr_y   = y;
224
225        dqdt_dmsg(1, "%s: level %d, x %d, y %d\n", __FUNCTION__, level, x, y);
226
227        if(matrix[x][y]->flags & DQDT_CLUSTER_UP)
228        {
229                child0  = matrix[x][y];
230                cluster = matrix[x][y]->home;
231                clstr_x = x;
232                clstr_y = y;
233                childs_nr ++;
234                cores_nr += child0->cores_nr;
235        }
236
237        if(matrix[x+1][y]->flags & DQDT_CLUSTER_UP)
238        {
239                child1  = matrix[x+1][y];
240                cluster = matrix[x+1][y]->home;
241                clstr_x = x+1;
242                clstr_y = y;
243                childs_nr ++;
244                cores_nr += child1->cores_nr;
245        }
246   
247        if(matrix[x][y+1]->flags & DQDT_CLUSTER_UP)
248        {
249                child2  = matrix[x][y+1];
250                cluster = matrix[x][y+1]->home;
251                clstr_x = x;
252                clstr_y = y+1;
253                childs_nr ++;
254                cores_nr += child2->cores_nr;
255        }
256 
257        if(matrix[x+1][y+1]->flags & DQDT_CLUSTER_UP)
258        {
259                child3  = matrix[x+1][y+1];
260                cluster = matrix[x+1][y+1]->home;
261                clstr_x = x+1;
262                clstr_y = y+1;
263                childs_nr ++;
264                cores_nr += child3->cores_nr;
265        }
266 
267        req.type  = KMEM_GENERIC;
268        req.size  = sizeof(*ptr);
269        req.flags = AF_BOOT | AF_REMOTE | AF_ZERO;
270        req.ptr   = (cluster == NULL) ? current_cluster : cluster;
271
272        ptr = kmem_alloc(&req);
273 
274        if(ptr == NULL)
275                return NULL;
276
277        ptr->level = level;
278        ptr->home  = matrix[clstr_x][clstr_y]->home;
279        ptr->flags = matrix[clstr_x][clstr_y]->flags;
280
281        if(cluster != NULL)
282        {
283                cluster->levels_tbl[level] = ptr;
284
285                ptr->children[0] = child0;
286                ptr->children[1] = child1;
287                ptr->children[2] = child2;
288                ptr->children[3] = child3;
289
290                matrix[x][y]->index     = 0;
291                matrix[x+1][y]->index   = 1;
292                matrix[x][y+1]->index   = 2;
293                matrix[x+1][y+1]->index = 3;
294        }
295
296        if(child0 == NULL)
297        {
298                req.ptr = matrix[x][y];
299                kmem_free(&req);
300        }
301        else
302                child0->parent = ptr;
303 
304        if(child1 == NULL)
305        {
306                req.ptr = matrix[x+1][y];
307                kmem_free(&req);
308        }
309        else
310                child1->parent = ptr;
311
312        if(child2 == NULL)
313        {
314                req.ptr = matrix[x][y+1];
315                kmem_free(&req);
316        }
317        else
318                child2->parent = ptr;
319
320        if(child3 == NULL)
321        {
322                req.ptr = matrix[x+1][y+1];
323                kmem_free(&req);
324        }
325        else
326                child3->parent = ptr;
327
328        ptr->cores_nr  = cores_nr;
329        ptr->childs_nr = childs_nr;
330       
331        dqdt_dmsg(1, "%s: level %d, x %d, y %d, childs_nr %d, cores_nr %d, isUp %s, done\n",
332                  __FUNCTION__,
333                  level,
334                  x,
335                  y,
336                  cores_nr,
337                  childs_nr,
338                  (cluster == NULL) ? "No" : "Yes");
339
340        return ptr;
341}
342
343error_t arch_dqdt_build(struct boot_info_s *info)
344{
345        struct arch_bib_header_s *header;
346        struct dqdt_cluster_s ***current;
347        struct dqdt_cluster_s ***next;
348        uint_t xmax;
349        uint_t ymax;
350        uint_t level;
351        uint_t x;
352        uint_t y;
353        error_t err;
354
355        header = (struct arch_bib_header_s*) info->arch_info;
356        xmax   = CONFIG_MAX_CLUSTER_ROOT;
357        ymax   = xmax;
358        level  = 1;
359 
360        current = arch_dqdt_alloc_matrix(xmax, ymax);
361
362        if(current == NULL)
363                return -1;
364 
365        err = arch_dqdt_chip_init(current,
366                                  &clusters_tbl[0],
367                                  header->x_max,
368                                  header->y_max);
369 
370        if(err) return err;
371 
372        while(xmax > 2)
373        {
374                dqdt_dmsg(1, "%s: current level %d, current xmax %d\n",
375                          __FUNCTION__,
376                          level,
377                          xmax);
378
379                next = arch_dqdt_alloc_matrix(xmax/2, ymax/2);
380   
381                if(next == NULL)
382                        return -xmax;
383   
384                for(x = 0; x < xmax; x += 2)
385                {
386                        for(y = 0; y < ymax; y += 2)
387                        {
388                                next[x/2][y/2] = arch_dqdt_make_cluster(current, level, x, y);
389
390                                if(next[x/2][y/2] == NULL)
391                                        return -xmax;
392                        }
393                }
394
395                level ++;
396                arch_dqdt_free_matrix(current, xmax, ymax);
397                current = next;
398                xmax = xmax/2;
399                ymax = ymax/2;
400        }
401
402        dqdt_dmsg(1, "%s: making dqdt_root, level %d\n", __FUNCTION__, level);
403
404        dqdt_root = arch_dqdt_make_cluster(current, level, 0, 0);
405        arch_dqdt_free_matrix(current, xmax, ymax);
406 
407        return 0;
408}
409
410#endif
Note: See TracBrowser for help on using the repository browser.