/*
** Copyright 2002/03, Thomas Kurschel. All rights reserved.
** Distributed under the terms of the MIT License.
*/

/*
        Part of Open SCSI bus manager

        Queuing of SCSI request

        Some words about queuing, i.e. making sure that no request
        gets stuck in some queue forever

        As long as the SIM accepts new reqs, XPT doesn't take care of 
        stuck requests - thus, peripheral drivers should use synced reqs 
        once in a while (or even always) to force the HBA to finish 
        previously submitted reqs. This is also important for non-queuing
        HBAs as in this case the queuing is done by the SCSI bus manager
        which uses elevator sort.

        Requests can be blocked by SIM or by the SCSI bus manager on a per-device
        or per-bus basis. There are three possible reasons:
        
        1. the hardware queue is too small
           - detected by bus manager automatically, or
           - detected by SIM which calls "requeue" for affected request
        2. SIM blocks bus/device explictely
        3. bus manager blocks bus/device explictly (currently used for 
           ordered requests)
        4. the device has queued requests or the bus has waiting devices resp.
           
        The first condition is automatically cleared when a request has
        been completed, but can be reset manually by the SIM. In the second and
        third cases, the SIM/bus manager must explictely unblock the bus/device.
        For easier testing,     the lock_count is the sum of the overflow bit, the 
        SIM lock count and the bus manager lock count. The blocking test is in
        scsi_check_enqueue_request() in scsi_io.c.
        
        If a bus/device is blocked or has waiting requests/devices, new requests 
        are added to a device-specific request queue in an elevator-sort style, 
        taking care that no ordered     requests are overtaken. Exceptions are 
        requeued request and autosense-requests, which are added first. Each bus 
        has a queue of non-blocked devices that have waiting requests. If a 
        device is to be added to this queue, it is always appended at tail 
        to ensure fair processing.
*/

#include "scsi_internal.h"
#include "queuing.h"


// add request to device queue, using evelvator sort
static void scsi_insert_new_request( scsi_device_info *device, 
        scsi_ccb *new_request )
{
        scsi_ccb *first, *last, *before, *next;
        
        SHOW_FLOW( 3, "inserting new_request=%p, pos=%" B_PRId64, new_request,
                new_request->sort );
        
        first = device->queued_reqs;
        
        if( first == NULL ) {
                SHOW_FLOW0( 1, "no other queued request" );
                scsi_add_req_queue_first( new_request );
                return;
        }
        
        SHOW_FLOW( 3, "first=%p, pos=%" B_PRId64 ", last_pos=%" B_PRId64, 
                first, first->sort, device->last_sort );

        // don't let syncs bypass others
        if( new_request->ordered ) {
                SHOW_FLOW0( 1, "adding synced request to tail" );
                scsi_add_req_queue_last( new_request );
                return;
        }
        
        if( new_request->sort < 0 ) {
                SHOW_FLOW0( 1, "adding unsortable request to tail" );
                scsi_add_req_queue_last( new_request );
                return;
        }

        // to reduce head seek time, we have three goals:
        // - sort request accendingly according to head position
        //   as as disks use to read ahead and not backwards
        // - ordered accesses can neither get overtaken by or overtake other requests
        //
        // in general, we only have block position, so head, track or
        // whatever specific optimizations can only be done by the disks
        // firmware;
        //
        // thus, sorting is done ascendingly with only a few exceptions:
        // - if position of request to be inserted is between current
        //   (i.e. last) position and position of first queued request, 
        //   insert it as first queue entry; i.e. we get descending order
        // - if position of first queued request is before current position
        //   and position of new req is before first queued request, add it 
        //   as first queue entry; i.e. the new and the (previously) first 
        //   request are sorted monotically increasing
        //
        // the first exception should help if the queue is short (not sure
        // whether this actually hurts if we have a long queue), the
        // second one maximizes monotonic ranges
        last = first->prev;
        
        if( (device->last_sort <= new_request->sort &&
                 new_request->sort <= first->sort) ||
                (first->sort < device->last_sort &&
                 new_request->sort <= first->sort) ) 
        {
                // these are the exceptions described above
                SHOW_FLOW0( 3, "trying to insert req at head of device req queue" );
                
                // we should have a new first request, make sure we don't bypass syncs
                for( before = last; !before->ordered; ) {
                        before = before->prev;
                        if( before == last )
                                break;
                }
                
                if( !before->ordered ) {
                        SHOW_FLOW0( 1, "scheduled request in front of all other reqs of device" );
                        scsi_add_req_queue_first( new_request );
                        return;
                } else
                        SHOW_FLOW0( 1, "req would bypass ordered request" );
        }
        
        // the insertion sort loop ignores ordered flag of last request, 
        // so check that here
        if( last->ordered ) {
                SHOW_FLOW0( 1, "last entry is ordered, adding new request as last" );
                scsi_add_req_queue_last( new_request );
                return;
        }
        
        SHOW_FLOW0( 3, "performing insertion sort" );

        // insertion sort starts with last entry to avoid unnecessary overtaking
        for( before = last->prev, next = last; 
                 before != last && !before->ordered; 
                 next = before, before = before->prev ) 
        {
                if( before->sort <= new_request->sort && new_request->sort <= next->sort )
                        break;
        }
        
        // if we bumped into ordered request, append new request at tail
        if( before->ordered ) {
                SHOW_FLOW0( 1, "overtaking ordered request in sorting - adding as last" );
                scsi_add_req_queue_last( new_request );
                return;
        }
        
        SHOW_FLOW( 1, "inserting after %p (pos=%" B_PRId64 ") and before %p (pos=%" B_PRId64 ")", 
                before, before->sort, next, next->sort );

        // if we haven't found a proper position, we automatically insert 
        // new request as last because request list is circular;
        // don't check whether we added request as first as this is impossible
        new_request->next = next;
        new_request->prev = before;
        next->prev = new_request;
        before->next = new_request;
}


// add request to end of device queue and device to bus queue
// used for normal requests
void scsi_add_queued_request( scsi_ccb *request )
{
        scsi_device_info *device = request->device;
        
        SHOW_FLOW0( 3, "" );

        request->state = SCSI_STATE_QUEUED;
        scsi_insert_new_request( device, request );
        
/*      {
                scsi_ccb *tmp = device->queued_reqs;
                
                dprintf( "pos=%lld, to_insert=%lld; ", device->last_sort,
                        request->sort );
                
                do {
                        dprintf( "%lld, %s", tmp->sort, tmp->next == device->queued_reqs ? "\n" : "" );
                        tmp = tmp->next;
                } while( tmp != device->queued_reqs );
        }*/

        // if device is not deliberately locked, mark it as waiting
        if( device->lock_count == 0 ) {
                SHOW_FLOW0( 3, "mark device as waiting" );
                scsi_add_device_queue_last( device );
        }
}


// add request to begin of device queue and device to bus queue
// used only for auto-sense request
void scsi_add_queued_request_first( scsi_ccb *request )
{
        scsi_device_info *device = request->device;
        
        SHOW_FLOW0( 3, "" );

        request->state = SCSI_STATE_QUEUED;
        scsi_add_req_queue_first( request );

        // if device is not deliberately locked, mark it as waiting
        if( device->lock_count == 0 ) {
                SHOW_FLOW0( 3, "mark device as waiting" );
                // make device first in bus queue to execute sense ASAP
                scsi_add_device_queue_first( device );
        }
}


// remove requests from queue, removing device from queue if idle
void scsi_remove_queued_request( scsi_ccb *request )
{
        scsi_remove_req_queue( request );
        
        if( request->device->queued_reqs == NULL )
                scsi_remove_device_queue( request->device );
}


// explictely unblock bus
static void scsi_unblock_bus_int( scsi_bus_info *bus, bool by_SIM )
{
        bool was_servicable, start_retry;
        
        SHOW_FLOW0( 3, "" );

        mutex_lock( &bus->mutex );
        
        was_servicable = scsi_can_service_bus( bus );

        scsi_unblock_bus_noresume( bus, by_SIM );
        
        start_retry = !was_servicable && scsi_can_service_bus( bus );

        mutex_unlock( &bus->mutex );
        
        if( start_retry )
                release_sem( bus->start_service );
}


// explicitely unblock bus as requested by SIM
void scsi_unblock_bus( scsi_bus_info *bus )
{
        scsi_unblock_bus_int( bus, true );
}


// explicitly unblock device
static void scsi_unblock_device_int( scsi_device_info *device, bool by_SIM )
{
        scsi_bus_info *bus = device->bus;
        bool was_servicable, start_retry;
        
        SHOW_FLOW0( 3, "" );
        
        mutex_lock( &bus->mutex );
        
        was_servicable = scsi_can_service_bus( bus );

        scsi_unblock_device_noresume( device, by_SIM );
        
        // add to bus queue if not locked explicitly anymore and requests are waiting
        if( device->lock_count == 0 && device->queued_reqs != NULL )
                scsi_add_device_queue_last( device );
        
        start_retry = !was_servicable && scsi_can_service_bus( bus );

        mutex_unlock( &bus->mutex );
        
        if( start_retry )
                release_sem( bus->start_service );
}


// explicitely unblock device as requested by SIM
void scsi_unblock_device( scsi_device_info *device )
{
        return scsi_unblock_device_int( device, true );
}


// SIM signals that it can handle further requests for this bus
void scsi_cont_send_bus( scsi_bus_info *bus )
{
        bool was_servicable, start_retry;
        
        SHOW_FLOW0( 3, "" );
        
        mutex_lock( &bus->mutex );
        
        was_servicable = scsi_can_service_bus( bus );

        scsi_clear_bus_overflow( bus ); 
        
        start_retry = !was_servicable && scsi_can_service_bus( bus );
                                
        mutex_unlock( &bus->mutex );

        if( start_retry )
                release_sem_etc( bus->start_service, 1, 0/*B_DO_NOT_RESCHEDULE*/ );
}


// SIM signals that it can handle further requests for this device
void scsi_cont_send_device( scsi_device_info *device )
{
        scsi_bus_info *bus = device->bus;
        bool was_servicable, start_retry;
        
        SHOW_FLOW0( 3, "" );
        
        mutex_lock( &bus->mutex );
        
        was_servicable = scsi_can_service_bus( bus );
        
        if( device->sim_overflow ) {                    
                device->sim_overflow = false;
                --device->lock_count;
                
                // add to bus queue if not locked explicitly anymore and requests are waiting
                if( device->lock_count == 0 && device->queued_reqs != NULL )
                        scsi_add_device_queue_last( device );
        }

        // no device overflow implicits no bus overflow
        // (and if not, we'll detect that on next submit)
        scsi_clear_bus_overflow( bus );
        
        start_retry = !was_servicable && scsi_can_service_bus( bus );
                                
        mutex_unlock( &bus->mutex );
        
        // tell service thread if there are pending requests which
        // weren't pending before       
        if( start_retry )
                release_sem_etc( bus->start_service, 1, 0/*B_DO_NOT_RESCHEDULE*/ );
}


// explicitly block bus
static void scsi_block_bus_int( scsi_bus_info *bus, bool by_SIM )
{
        SHOW_FLOW0( 3, "" );
        
        mutex_lock( &bus->mutex );

        scsi_block_bus_nolock( bus, by_SIM );
        
        mutex_unlock( &bus->mutex );
}


// explicitly block bus as requested by SIM
void scsi_block_bus( scsi_bus_info *bus )
{
        return scsi_block_bus_int( bus, true );
}


// explicitly block device
static void scsi_block_device_int( scsi_device_info *device, bool by_SIM )
{
        scsi_bus_info *bus = device->bus;
        
        SHOW_FLOW0( 3, "" );
        
        mutex_lock( &bus->mutex );

        scsi_block_device_nolock( device, by_SIM );

        // remove device from bus queue as it cannot be processed anymore
        scsi_remove_device_queue( device );
        
        mutex_unlock( &bus->mutex );
}


// explicitly block device as requested by SIM
void scsi_block_device( scsi_device_info *device )
{
        return scsi_block_device_int( device, true );
}