1 /*- 2 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 */ 27 28 #include <sys/cdefs.h> 29 #include <sys/time.h> 30 31 #include <assert.h> 32 #include <stdlib.h> 33 #include <string.h> 34 35 #include "cacheplcs.h" 36 #include "debug.h" 37 38 static void cache_fifo_policy_update_item(struct cache_policy_ *, 39 struct cache_policy_item_ *); 40 static void cache_lfu_policy_add_item(struct cache_policy_ *, 41 struct cache_policy_item_ *); 42 static struct cache_policy_item_ * cache_lfu_policy_create_item(void); 43 static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *); 44 static struct cache_policy_item_ *cache_lfu_policy_get_first_item( 45 struct cache_policy_ *); 46 static struct cache_policy_item_ *cache_lfu_policy_get_last_item( 47 struct cache_policy_ *); 48 static struct cache_policy_item_ *cache_lfu_policy_get_next_item( 49 struct cache_policy_ *, struct cache_policy_item_ *); 50 static struct cache_policy_item_ *cache_lfu_policy_get_prev_item( 51 struct cache_policy_ *, struct cache_policy_item_ *); 52 static void cache_lfu_policy_remove_item(struct cache_policy_ *, 53 struct cache_policy_item_ *); 54 static void cache_lfu_policy_update_item(struct cache_policy_ *, 55 struct cache_policy_item_ *); 56 static void cache_lru_policy_update_item(struct cache_policy_ *, 57 struct cache_policy_item_ *); 58 static void cache_queue_policy_add_item(struct cache_policy_ *, 59 struct cache_policy_item_ *); 60 static struct cache_policy_item_ * cache_queue_policy_create_item(void); 61 static void cache_queue_policy_destroy_item(struct cache_policy_item_ *); 62 static struct cache_policy_item_ *cache_queue_policy_get_first_item( 63 struct cache_policy_ *); 64 static struct cache_policy_item_ *cache_queue_policy_get_last_item( 65 struct cache_policy_ *); 66 static struct cache_policy_item_ *cache_queue_policy_get_next_item( 67 struct cache_policy_ *, struct cache_policy_item_ *); 68 static struct cache_policy_item_ *cache_queue_policy_get_prev_item( 69 struct cache_policy_ *, struct cache_policy_item_ *); 70 static void cache_queue_policy_remove_item(struct cache_policy_ *, 71 struct cache_policy_item_ *); 72 static void destroy_cache_queue_policy(struct cache_queue_policy_ *); 73 static struct cache_queue_policy_ *init_cache_queue_policy(void); 74 75 /* 76 * All cache_queue_policy_XXX functions below will be used to fill 77 * the cache_queue_policy structure. They implement the most functionality of 78 * LRU and FIFO policies. LRU and FIFO policies are actually the 79 * cache_queue_policy_ with cache_update_item function changed. 80 */ 81 static struct cache_policy_item_ * 82 cache_queue_policy_create_item(void) 83 { 84 struct cache_queue_policy_item_ *retval; 85 86 TRACE_IN(cache_queue_policy_create_item); 87 retval = calloc(1, 88 sizeof(*retval)); 89 assert(retval != NULL); 90 91 TRACE_OUT(cache_queue_policy_create_item); 92 return ((struct cache_policy_item_ *)retval); 93 } 94 95 static void 96 cache_queue_policy_destroy_item(struct cache_policy_item_ *item) 97 { 98 99 TRACE_IN(cache_queue_policy_destroy_item); 100 assert(item != NULL); 101 free(item); 102 TRACE_OUT(cache_queue_policy_destroy_item); 103 } 104 105 static void 106 cache_queue_policy_add_item(struct cache_policy_ *policy, 107 struct cache_policy_item_ *item) 108 { 109 struct cache_queue_policy_ *queue_policy; 110 struct cache_queue_policy_item_ *queue_item; 111 112 TRACE_IN(cache_queue_policy_add_item); 113 queue_policy = (struct cache_queue_policy_ *)policy; 114 queue_item = (struct cache_queue_policy_item_ *)item; 115 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 116 TRACE_OUT(cache_queue_policy_add_item); 117 } 118 119 static void 120 cache_queue_policy_remove_item(struct cache_policy_ *policy, 121 struct cache_policy_item_ *item) 122 { 123 struct cache_queue_policy_ *queue_policy; 124 struct cache_queue_policy_item_ *queue_item; 125 126 TRACE_IN(cache_queue_policy_remove_item); 127 queue_policy = (struct cache_queue_policy_ *)policy; 128 queue_item = (struct cache_queue_policy_item_ *)item; 129 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 130 TRACE_OUT(cache_queue_policy_remove_item); 131 } 132 133 static struct cache_policy_item_ * 134 cache_queue_policy_get_first_item(struct cache_policy_ *policy) 135 { 136 struct cache_queue_policy_ *queue_policy; 137 138 TRACE_IN(cache_queue_policy_get_first_item); 139 queue_policy = (struct cache_queue_policy_ *)policy; 140 TRACE_OUT(cache_queue_policy_get_first_item); 141 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head)); 142 } 143 144 static struct cache_policy_item_ * 145 cache_queue_policy_get_last_item(struct cache_policy_ *policy) 146 { 147 struct cache_queue_policy_ *queue_policy; 148 149 TRACE_IN(cache_queue_policy_get_last_item); 150 queue_policy = (struct cache_queue_policy_ *)policy; 151 TRACE_OUT(cache_queue_policy_get_last_item); 152 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head, 153 cache_queue_policy_head_)); 154 } 155 156 static struct cache_policy_item_ * 157 cache_queue_policy_get_next_item(struct cache_policy_ *policy, 158 struct cache_policy_item_ *item) 159 { 160 struct cache_queue_policy_item_ *queue_item; 161 162 TRACE_IN(cache_queue_policy_get_next_item); 163 queue_item = (struct cache_queue_policy_item_ *)item; 164 165 TRACE_OUT(cache_queue_policy_get_next_item); 166 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 167 } 168 169 static struct cache_policy_item_ * 170 cache_queue_policy_get_prev_item(struct cache_policy_ *policy, 171 struct cache_policy_item_ *item) 172 { 173 struct cache_queue_policy_item_ *queue_item; 174 175 TRACE_IN(cache_queue_policy_get_prev_item); 176 queue_item = (struct cache_queue_policy_item_ *)item; 177 178 TRACE_OUT(cache_queue_policy_get_prev_item); 179 return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item, 180 cache_queue_policy_head_, entries)); 181 } 182 183 /* 184 * Initializes cache_queue_policy_ by filling the structure with the functions 185 * pointers, defined above 186 */ 187 static struct cache_queue_policy_ * 188 init_cache_queue_policy(void) 189 { 190 struct cache_queue_policy_ *retval; 191 192 TRACE_IN(init_cache_queue_policy); 193 retval = calloc(1, 194 sizeof(*retval)); 195 assert(retval != NULL); 196 197 retval->parent_data.create_item_func = cache_queue_policy_create_item; 198 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 199 200 retval->parent_data.add_item_func = cache_queue_policy_add_item; 201 retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 202 203 retval->parent_data.get_first_item_func = 204 cache_queue_policy_get_first_item; 205 retval->parent_data.get_last_item_func = 206 cache_queue_policy_get_last_item; 207 retval->parent_data.get_next_item_func = 208 cache_queue_policy_get_next_item; 209 retval->parent_data.get_prev_item_func = 210 cache_queue_policy_get_prev_item; 211 212 TAILQ_INIT(&retval->head); 213 TRACE_OUT(init_cache_queue_policy); 214 return (retval); 215 } 216 217 static void 218 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 219 { 220 struct cache_queue_policy_item_ *queue_item; 221 222 TRACE_IN(destroy_cache_queue_policy); 223 while (!TAILQ_EMPTY(&queue_policy->head)) { 224 queue_item = TAILQ_FIRST(&queue_policy->head); 225 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 226 cache_queue_policy_destroy_item( 227 (struct cache_policy_item_ *)queue_item); 228 } 229 free(queue_policy); 230 TRACE_OUT(destroy_cache_queue_policy); 231 } 232 233 /* 234 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything, 235 * when the cache element is updated. So it always stays in its initial 236 * position in the queue - that is exactly the FIFO functionality. 237 */ 238 static void 239 cache_fifo_policy_update_item(struct cache_policy_ *policy, 240 struct cache_policy_item_ *item) 241 { 242 243 TRACE_IN(cache_fifo_policy_update_item); 244 /* policy and item arguments are ignored */ 245 TRACE_OUT(cache_fifo_policy_update_item); 246 } 247 248 struct cache_policy_ * 249 init_cache_fifo_policy(void) 250 { 251 struct cache_queue_policy_ *retval; 252 253 TRACE_IN(init_cache_fifo_policy); 254 retval = init_cache_queue_policy(); 255 retval->parent_data.update_item_func = cache_fifo_policy_update_item; 256 257 TRACE_OUT(init_cache_fifo_policy); 258 return ((struct cache_policy_ *)retval); 259 } 260 261 void 262 destroy_cache_fifo_policy(struct cache_policy_ *policy) 263 { 264 struct cache_queue_policy_ *queue_policy; 265 266 TRACE_IN(destroy_cache_fifo_policy); 267 queue_policy = (struct cache_queue_policy_ *)policy; 268 destroy_cache_queue_policy(queue_policy); 269 TRACE_OUT(destroy_cache_fifo_policy); 270 } 271 272 /* 273 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache 274 * element is moved to the end of the queue - so it would be deleted in last 275 * turn. That is exactly the LRU policy functionality. 276 */ 277 static void 278 cache_lru_policy_update_item(struct cache_policy_ *policy, 279 struct cache_policy_item_ *item) 280 { 281 struct cache_queue_policy_ *queue_policy; 282 struct cache_queue_policy_item_ *queue_item; 283 284 TRACE_IN(cache_lru_policy_update_item); 285 queue_policy = (struct cache_queue_policy_ *)policy; 286 queue_item = (struct cache_queue_policy_item_ *)item; 287 288 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 289 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 290 TRACE_OUT(cache_lru_policy_update_item); 291 } 292 293 struct cache_policy_ * 294 init_cache_lru_policy(void) 295 { 296 struct cache_queue_policy_ *retval; 297 298 TRACE_IN(init_cache_lru_policy); 299 retval = init_cache_queue_policy(); 300 retval->parent_data.update_item_func = cache_lru_policy_update_item; 301 302 TRACE_OUT(init_cache_lru_policy); 303 return ((struct cache_policy_ *)retval); 304 } 305 306 void 307 destroy_cache_lru_policy(struct cache_policy_ *policy) 308 { 309 struct cache_queue_policy_ *queue_policy; 310 311 TRACE_IN(destroy_cache_lru_policy); 312 queue_policy = (struct cache_queue_policy_ *)policy; 313 destroy_cache_queue_policy(queue_policy); 314 TRACE_OUT(destroy_cache_lru_policy); 315 } 316 317 /* 318 * LFU (least frequently used) policy implementation differs much from the 319 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_ 320 * functions are implemented specifically for this policy. The idea of this 321 * policy is to represent frequency (real number) as the integer number and 322 * use it as the index in the array. Each array's element is 323 * the list of elements. For example, if we have the 100-elements 324 * array for this policy, the elements with frequency 0.1 (calls per-second) 325 * would be in 10th element of the array. 326 */ 327 static struct cache_policy_item_ * 328 cache_lfu_policy_create_item(void) 329 { 330 struct cache_lfu_policy_item_ *retval; 331 332 TRACE_IN(cache_lfu_policy_create_item); 333 retval = calloc(1, 334 sizeof(*retval)); 335 assert(retval != NULL); 336 337 TRACE_OUT(cache_lfu_policy_create_item); 338 return ((struct cache_policy_item_ *)retval); 339 } 340 341 static void 342 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 343 { 344 345 TRACE_IN(cache_lfu_policy_destroy_item); 346 assert(item != NULL); 347 free(item); 348 TRACE_OUT(cache_lfu_policy_destroy_item); 349 } 350 351 /* 352 * When placed in the LFU policy queue for the first time, the maximum 353 * frequency is assigned to the element 354 */ 355 static void 356 cache_lfu_policy_add_item(struct cache_policy_ *policy, 357 struct cache_policy_item_ *item) 358 { 359 struct cache_lfu_policy_ *lfu_policy; 360 struct cache_lfu_policy_item_ *lfu_item; 361 362 TRACE_IN(cache_lfu_policy_add_item); 363 lfu_policy = (struct cache_lfu_policy_ *)policy; 364 lfu_item = (struct cache_lfu_policy_item_ *)item; 365 366 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 367 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 368 lfu_item, entries); 369 TRACE_OUT(cache_lfu_policy_add_item); 370 } 371 372 /* 373 * On each update the frequency of the element is recalculated and, if it 374 * changed, the element would be moved to the another place in the array. 375 */ 376 static void 377 cache_lfu_policy_update_item(struct cache_policy_ *policy, 378 struct cache_policy_item_ *item) 379 { 380 struct cache_lfu_policy_ *lfu_policy; 381 struct cache_lfu_policy_item_ *lfu_item; 382 int index; 383 384 TRACE_IN(cache_lfu_policy_update_item); 385 lfu_policy = (struct cache_lfu_policy_ *)policy; 386 lfu_item = (struct cache_lfu_policy_item_ *)item; 387 388 /* 389 * We calculate the square of the request_count to avoid grouping of 390 * all elements at the start of the array (for example, if array size is 391 * 100 and most of its elements has frequency below the 0.01, they 392 * all would be grouped in the first array's position). Other 393 * techniques should be used here later to ensure, that elements are 394 * equally distributed in the array and not grouped in its beginning. 395 */ 396 if (lfu_item->parent_data.last_request_time.tv_sec != 397 lfu_item->parent_data.creation_time.tv_sec) { 398 index = ((double)lfu_item->parent_data.request_count * 399 (double)lfu_item->parent_data.request_count / 400 (lfu_item->parent_data.last_request_time.tv_sec - 401 lfu_item->parent_data.creation_time.tv_sec + 1)) * 402 CACHELIB_MAX_FREQUENCY; 403 if (index >= CACHELIB_MAX_FREQUENCY) 404 index = CACHELIB_MAX_FREQUENCY - 1; 405 } else 406 index = CACHELIB_MAX_FREQUENCY - 1; 407 408 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 409 entries); 410 lfu_item->frequency = index; 411 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 412 413 TRACE_OUT(cache_lfu_policy_update_item); 414 } 415 416 static void 417 cache_lfu_policy_remove_item(struct cache_policy_ *policy, 418 struct cache_policy_item_ *item) 419 { 420 struct cache_lfu_policy_ *lfu_policy; 421 struct cache_lfu_policy_item_ *lfu_item; 422 423 TRACE_IN(cache_lfu_policy_remove_item); 424 lfu_policy = (struct cache_lfu_policy_ *)policy; 425 lfu_item = (struct cache_lfu_policy_item_ *)item; 426 427 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 428 entries); 429 TRACE_OUT(cache_lfu_policy_remove_item); 430 } 431 432 static struct cache_policy_item_ * 433 cache_lfu_policy_get_first_item(struct cache_policy_ *policy) 434 { 435 struct cache_lfu_policy_ *lfu_policy; 436 struct cache_lfu_policy_item_ *lfu_item; 437 int i; 438 439 TRACE_IN(cache_lfu_policy_get_first_item); 440 lfu_item = NULL; 441 lfu_policy = (struct cache_lfu_policy_ *)policy; 442 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 443 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 444 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 445 break; 446 } 447 448 TRACE_OUT(cache_lfu_policy_get_first_item); 449 return ((struct cache_policy_item_ *)lfu_item); 450 } 451 452 static struct cache_policy_item_ * 453 cache_lfu_policy_get_last_item(struct cache_policy_ *policy) 454 { 455 struct cache_lfu_policy_ *lfu_policy; 456 struct cache_lfu_policy_item_ *lfu_item; 457 int i; 458 459 TRACE_IN(cache_lfu_policy_get_last_item); 460 lfu_item = NULL; 461 lfu_policy = (struct cache_lfu_policy_ *)policy; 462 for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i) 463 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 464 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 465 cache_lfu_policy_group_); 466 break; 467 } 468 469 TRACE_OUT(cache_lfu_policy_get_last_item); 470 return ((struct cache_policy_item_ *)lfu_item); 471 } 472 473 static struct cache_policy_item_ * 474 cache_lfu_policy_get_next_item(struct cache_policy_ *policy, 475 struct cache_policy_item_ *item) 476 { 477 struct cache_lfu_policy_ *lfu_policy; 478 struct cache_lfu_policy_item_ *lfu_item; 479 int i; 480 481 TRACE_IN(cache_lfu_policy_get_next_item); 482 lfu_policy = (struct cache_lfu_policy_ *)policy; 483 lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries); 484 if (lfu_item == NULL) 485 { 486 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1; 487 i < CACHELIB_MAX_FREQUENCY; ++i) { 488 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 489 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 490 break; 491 } 492 } 493 } 494 495 TRACE_OUT(cache_lfu_policy_get_next_item); 496 return ((struct cache_policy_item_ *)lfu_item); 497 } 498 499 static struct cache_policy_item_ * 500 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 501 struct cache_policy_item_ *item) 502 { 503 struct cache_lfu_policy_ *lfu_policy; 504 struct cache_lfu_policy_item_ *lfu_item; 505 int i; 506 507 TRACE_IN(cache_lfu_policy_get_prev_item); 508 lfu_policy = (struct cache_lfu_policy_ *)policy; 509 lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item, 510 cache_lfu_policy_group_, entries); 511 if (lfu_item == NULL) 512 { 513 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 514 i >= 0; --i) 515 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 516 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 517 cache_lfu_policy_group_); 518 break; 519 } 520 } 521 522 TRACE_OUT(cache_lfu_policy_get_prev_item); 523 return ((struct cache_policy_item_ *)lfu_item); 524 } 525 526 /* 527 * Initializes the cache_policy_ structure by filling it with appropriate 528 * functions pointers 529 */ 530 struct cache_policy_ * 531 init_cache_lfu_policy(void) 532 { 533 int i; 534 struct cache_lfu_policy_ *retval; 535 536 TRACE_IN(init_cache_lfu_policy); 537 retval = calloc(1, 538 sizeof(*retval)); 539 assert(retval != NULL); 540 541 retval->parent_data.create_item_func = cache_lfu_policy_create_item; 542 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 543 544 retval->parent_data.add_item_func = cache_lfu_policy_add_item; 545 retval->parent_data.update_item_func = cache_lfu_policy_update_item; 546 retval->parent_data.remove_item_func = cache_lfu_policy_remove_item; 547 548 retval->parent_data.get_first_item_func = 549 cache_lfu_policy_get_first_item; 550 retval->parent_data.get_last_item_func = 551 cache_lfu_policy_get_last_item; 552 retval->parent_data.get_next_item_func = 553 cache_lfu_policy_get_next_item; 554 retval->parent_data.get_prev_item_func = 555 cache_lfu_policy_get_prev_item; 556 557 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 558 TAILQ_INIT(&(retval->groups[i])); 559 560 TRACE_OUT(init_cache_lfu_policy); 561 return ((struct cache_policy_ *)retval); 562 } 563 564 void 565 destroy_cache_lfu_policy(struct cache_policy_ *policy) 566 { 567 int i; 568 struct cache_lfu_policy_ *lfu_policy; 569 struct cache_lfu_policy_item_ *lfu_item; 570 571 TRACE_IN(destroy_cache_lfu_policy); 572 lfu_policy = (struct cache_lfu_policy_ *)policy; 573 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) { 574 while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 575 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 576 TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item, 577 entries); 578 cache_lfu_policy_destroy_item( 579 (struct cache_policy_item_ *)lfu_item); 580 } 581 } 582 free(policy); 583 TRACE_OUT(destroy_cache_lfu_policy); 584 } 585