Changeset c08072ce in rtems for cpukit/libblock


Ignore:
Timestamp:
Mar 14, 2012, 7:45:53 AM (8 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, master
Children:
a309a79
Parents:
f9fd0c2
git-author:
Sebastian Huber <sebastian.huber@…> (03/14/12 07:45:53)
git-committer:
Sebastian Huber <sebastian.huber@…> (03/14/12 09:48:54)
Message:

PR2040: libblock: Avoid erased blocks starvation

The compaction process needs erased blocks. It is only possible to
erase an entire segment. Thus in order to make a progress we always
need enough erased blocks to empty a used or available segment which can
be erased in turn. A (possibly the worst case) lower bound of erased
blocks is the block count of the largest segment. The number of
unavailable blocks specified by the configuration will be used to
determine the erase blocks starvation situation. The number of
unavailable blocks must be greater than or equal to the number of blocks
in the largest segment.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • cpukit/libblock/src/flashdisk.c

    rf9fd0c2 rc08072ce  
    349349  }
    350350  return ret;
     351}
     352
     353static bool
     354rtems_fdisk_is_erased_blocks_starvation (const rtems_flashdisk* fd)
     355{
     356  return fd->erased_blocks < fd->unavail_blocks;
    351357}
    352358
     
    13101316}
    13111317
     1318static int
     1319rtems_fdisk_recycle_segment (rtems_flashdisk*         fd,
     1320                                    rtems_fdisk_segment_ctl* ssc,
     1321                                    rtems_fdisk_segment_ctl* dsc,
     1322                                    uint32_t *pages)
     1323{
     1324  int      ret;
     1325  uint32_t spage;
     1326  uint32_t used = 0;
     1327  uint32_t active = 0;
     1328
     1329  for (spage = 0; spage < ssc->pages; spage++)
     1330  {
     1331    uint32_t               dst_pages;
     1332    rtems_fdisk_page_desc* spd = &ssc->page_descriptors[spage];
     1333
     1334    if (rtems_fdisk_page_desc_flags_set (spd, RTEMS_FDISK_PAGE_ACTIVE) &&
     1335        !rtems_fdisk_page_desc_flags_set (spd, RTEMS_FDISK_PAGE_USED))
     1336    {
     1337      rtems_fdisk_page_desc* dpd;
     1338      uint32_t               dpage;
     1339
     1340      dpage = rtems_fdisk_seg_next_available_page (dsc);
     1341      dpd   = &dsc->page_descriptors[dpage];
     1342
     1343      active++;
     1344
     1345      if (dpage >= dsc->pages)
     1346      {
     1347        rtems_fdisk_error ("recycle: %02d-%03d: " \
     1348                           "no page desc available: %d",
     1349                           dsc->device, dsc->segment,
     1350                           rtems_fdisk_seg_pages_available (dsc));
     1351        dsc->failed = true;
     1352        rtems_fdisk_queue_segment (fd, dsc);
     1353        rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
     1354        return EIO;
     1355      }
     1356
     1357#if RTEMS_FDISK_TRACE
     1358      rtems_fdisk_info (fd, "recycle: %02d-%03d-%03d=>%02d-%03d-%03d",
     1359                        ssc->device, ssc->segment, spage,
     1360                        dsc->device, dsc->segment, dpage);
     1361#endif
     1362      ret = rtems_fdisk_seg_copy_page (fd, ssc,
     1363                                       spage + ssc->pages_desc,
     1364                                       dsc,
     1365                                       dpage + dsc->pages_desc);
     1366      if (ret)
     1367      {
     1368        rtems_fdisk_error ("recycle: %02d-%03d-%03d=>" \
     1369                           "%02d-%03d-%03d: "             \
     1370                           "copy page failed: %s (%d)",
     1371                           ssc->device, ssc->segment, spage,
     1372                           dsc->device, dsc->segment, dpage,
     1373                           strerror (ret), ret);
     1374        rtems_fdisk_queue_segment (fd, dsc);
     1375        rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
     1376        return ret;
     1377      }
     1378
     1379      *dpd = *spd;
     1380
     1381      ret = rtems_fdisk_seg_write_page_desc (fd,
     1382                                             dsc,
     1383                                             dpage, dpd);
     1384
     1385      if (ret)
     1386      {
     1387        rtems_fdisk_error ("recycle: %02d-%03d-%03d=>"   \
     1388                           "%02d-%03d-%03d: copy pd failed: %s (%d)",
     1389                           ssc->device, ssc->segment, spage,
     1390                           dsc->device, dsc->segment, dpage,
     1391                           strerror (ret), ret);
     1392        rtems_fdisk_queue_segment (fd, dsc);
     1393        rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
     1394        return ret;
     1395      }
     1396
     1397      dsc->pages_active++;
     1398
     1399      /*
     1400       * No need to set the used bit on the source page as the
     1401       * segment will be erased. Power down could be a problem.
     1402       * We do the stats to make sure everything is as it should
     1403       * be.
     1404       */
     1405
     1406      ssc->pages_active--;
     1407      ssc->pages_used++;
     1408
     1409      fd->blocks[spd->block].segment = dsc;
     1410      fd->blocks[spd->block].page    = dpage;
     1411
     1412      /*
     1413       * Place the segment on to the correct queue.
     1414       */
     1415      rtems_fdisk_queue_segment (fd, dsc);
     1416
     1417      /*
     1418       * Get new destination segment if necessary.
     1419       */
     1420      dst_pages = rtems_fdisk_seg_pages_available (dsc);
     1421      if (dst_pages == 0)
     1422      {
     1423        dsc = rtems_fdisk_seg_most_available (&fd->available);
     1424        if (!dsc)
     1425        {
     1426          rtems_fdisk_error ("recycle: no available dst segment");
     1427          return EIO;
     1428        }
     1429      }
     1430
     1431      (*pages)--;
     1432    }
     1433    else if (rtems_fdisk_page_desc_erased (spd))
     1434    {
     1435      --fd->erased_blocks;
     1436    }
     1437    else
     1438    {
     1439      used++;
     1440    }
     1441  }
     1442
     1443#if RTEMS_FDISK_TRACE
     1444  rtems_fdisk_printf (fd, "ssc end: %d-%d: p=%ld, a=%ld, u=%ld",
     1445                      ssc->device, ssc->segment,
     1446                      pages, active, used);
     1447#endif
     1448  if (ssc->pages_active != 0)
     1449  {
     1450    rtems_fdisk_error ("compacting: ssc pages not 0: %d",
     1451                       ssc->pages_active);
     1452  }
     1453
     1454  ret = rtems_fdisk_erase_segment (fd, ssc);
     1455
     1456  return ret;
     1457}
     1458
    13121459/**
    13131460 * Compact the used segments to free what is available. Find the segment
    1314  * with the most avalable number of pages and see if we have
     1461 * with the most available number of pages and see if we have
    13151462 * used segments that will fit. The used queue is sorted on the least
    13161463 * number of active pages.
     
    13191466rtems_fdisk_compact (rtems_flashdisk* fd)
    13201467{
     1468  int ret;
     1469  rtems_fdisk_segment_ctl* dsc;
     1470  rtems_fdisk_segment_ctl* ssc;
    13211471  uint32_t compacted_segs = 0;
     1472  uint32_t pages;
     1473
     1474  if (rtems_fdisk_is_erased_blocks_starvation (fd))
     1475  {
     1476    ssc = rtems_fdisk_segment_queue_pop_head (&fd->used);
     1477    if (!ssc)
     1478      ssc = rtems_fdisk_segment_queue_pop_head (&fd->available);
     1479
     1480    if (ssc)
     1481    {
     1482      dsc = rtems_fdisk_seg_most_available (&fd->available);
     1483      if (dsc)
     1484      {
     1485        ret = rtems_fdisk_recycle_segment (fd, ssc, dsc, &pages);
     1486        if (ret)
     1487          return ret;
     1488      }
     1489      else
     1490      {
     1491        rtems_fdisk_error ("compacting: starvation");
     1492        return EIO;
     1493      }
     1494    }
     1495    else
     1496    {
     1497      rtems_fdisk_error ("compacting: nothing to recycle");
     1498      return EIO;
     1499    }
     1500  }
    13221501
    13231502  while (fd->used.head)
    13241503  {
    1325     rtems_fdisk_segment_ctl* dsc;
    1326     rtems_fdisk_segment_ctl* ssc;
    13271504    uint32_t                 dst_pages;
    13281505    uint32_t                 segments;
    1329     uint32_t                 pages;
    13301506
    13311507#if RTEMS_FDISK_TRACE
     
    13911567    while (pages)
    13921568    {
    1393       uint32_t spage;
    1394       int      ret;
    1395 
    13961569      ssc = rtems_fdisk_segment_queue_pop_head (&fd->used);
    13971570
    13981571      if (ssc)
    13991572      {
    1400         uint32_t used = 0;
    1401         uint32_t active = 0;
    1402         for (spage = 0; spage < ssc->pages; spage++)
    1403         {
    1404           rtems_fdisk_page_desc* spd = &ssc->page_descriptors[spage];
    1405 
    1406           if (rtems_fdisk_page_desc_flags_set (spd, RTEMS_FDISK_PAGE_ACTIVE) &&
    1407               !rtems_fdisk_page_desc_flags_set (spd, RTEMS_FDISK_PAGE_USED))
    1408           {
    1409             rtems_fdisk_page_desc* dpd;
    1410             uint32_t               dpage;
    1411 
    1412             dpage = rtems_fdisk_seg_next_available_page (dsc);
    1413             dpd   = &dsc->page_descriptors[dpage];
    1414 
    1415             active++;
    1416 
    1417             if (dpage >= dsc->pages)
    1418             {
    1419               rtems_fdisk_error ("compacting: %02d-%03d: " \
    1420                                  "no page desc available: %d",
    1421                                  dsc->device, dsc->segment,
    1422                                  rtems_fdisk_seg_pages_available (dsc));
    1423               dsc->failed = true;
    1424               rtems_fdisk_queue_segment (fd, dsc);
    1425               rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
    1426               return EIO;
    1427             }
    1428 
    1429 #if RTEMS_FDISK_TRACE
    1430             rtems_fdisk_info (fd, "compacting: %02d-%03d-%03d=>%02d-%03d-%03d",
    1431                               ssc->device, ssc->segment, spage,
    1432                               dsc->device, dsc->segment, dpage);
    1433 #endif
    1434             ret = rtems_fdisk_seg_copy_page (fd, ssc,
    1435                                              spage + ssc->pages_desc,
    1436                                              dsc,
    1437                                              dpage + dsc->pages_desc);
    1438             if (ret)
    1439             {
    1440               rtems_fdisk_error ("compacting: %02d-%03d-%03d=>" \
    1441                                  "%02d-%03d-%03d: "             \
    1442                                  "copy page failed: %s (%d)",
    1443                                  ssc->device, ssc->segment, spage,
    1444                                  dsc->device, dsc->segment, dpage,
    1445                                  strerror (ret), ret);
    1446               rtems_fdisk_queue_segment (fd, dsc);
    1447               rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
    1448               return ret;
    1449             }
    1450 
    1451             *dpd = *spd;
    1452 
    1453             ret = rtems_fdisk_seg_write_page_desc (fd,
    1454                                                    dsc,
    1455                                                    dpage, dpd);
    1456 
    1457             if (ret)
    1458             {
    1459               rtems_fdisk_error ("compacting: %02d-%03d-%03d=>"   \
    1460                                  "%02d-%03d-%03d: copy pd failed: %s (%d)",
    1461                                  ssc->device, ssc->segment, spage,
    1462                                  dsc->device, dsc->segment, dpage,
    1463                                  strerror (ret), ret);
    1464               rtems_fdisk_queue_segment (fd, dsc);
    1465               rtems_fdisk_segment_queue_push_head (&fd->used, ssc);
    1466               return ret;
    1467             }
    1468 
    1469             dsc->pages_active++;
    1470 
    1471             /*
    1472              * No need to set the used bit on the source page as the
    1473              * segment will be erased. Power down could be a problem.
    1474              * We do the stats to make sure everything is as it should
    1475              * be.
    1476              */
    1477 
    1478             ssc->pages_active--;
    1479             ssc->pages_used++;
    1480 
    1481             fd->blocks[spd->block].segment = dsc;
    1482             fd->blocks[spd->block].page    = dpage;
    1483 
    1484             /*
    1485              * Place the segment on to the correct queue.
    1486              */
    1487             rtems_fdisk_queue_segment (fd, dsc);
    1488 
    1489             pages--;
    1490           }
    1491           else
    1492             used++;
    1493         }
    1494 
    1495 #if RTEMS_FDISK_TRACE
    1496         rtems_fdisk_printf (fd, "ssc end: %d-%d: p=%ld, a=%ld, u=%ld",
    1497                             ssc->device, ssc->segment,
    1498                             pages, active, used);
    1499 #endif
    1500         if (ssc->pages_active != 0)
    1501         {
    1502           rtems_fdisk_error ("compacting: ssc pages not 0: %d",
    1503                              ssc->pages_active);
    1504         }
    1505 
    1506         ret = rtems_fdisk_erase_segment (fd, ssc);
    1507 
     1573        ret = rtems_fdisk_recycle_segment (fd, ssc, dsc, &pages);
    15081574        if (ret)
    15091575          return ret;
     
    20322098
    20332099      rtems_fdisk_queue_segment (fd, sc);
     2100
     2101      if (rtems_fdisk_is_erased_blocks_starvation (fd))
     2102        rtems_fdisk_compact (fd);
     2103
    20342104      return ret;
    20352105    }
Note: See TracChangeset for help on using the changeset viewer.