summaryrefslogtreecommitdiffstats
path: root/fs/ramfs
AgeCommit message (Expand)Author
2017-09-06mm: make pagevec_lookup() update indexJan Kara
2017-07-06ramfs: Implement show_optionsDavid Howells
2016-12-24Replace <asm/uaccess.h> with <linux/uaccess.h> globallyLinus Torvalds
2016-10-10Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/vir...Linus Torvalds
2016-10-10Merge remote-tracking branch 'ovl/rename2' into for-linusAl Viro
2016-10-08Merge remote-tracking branch 'jk/vfs' into work.miscAl Viro
2016-09-27fs: Replace CURRENT_TIME with current_time() for inode timestampsDeepa Dinamani
2016-09-27fs: rename "rename2" i_op to "rename"Miklos Szeredi
2016-09-27libfs: support RENAME_NOREPLACE in simple_rename()Miklos Szeredi
2016-09-22fs: Give dentry to inode_change_ok() instead of inodeJan Kara
2016-09-19ipc/shm: fix crash if CONFIG_SHMEM is not setKirill A. Shutemov
2016-05-20tmpfs/ramfs: fix VM_MAYSHARE mappings for NOMMURich Felker
2016-04-04mm, fs: get rid of PAGE_CACHE_* and page_cache_{get,release} macrosKirill A. Shutemov
2015-12-08don't put symlink bodies in pagecache into highmemAl Viro
2015-10-16mm, fs: obey gfp_mapping for add_to_page_cache()Michal Hocko
2015-04-15VFS: normal filesystems (and lustre): d_inode() annotationsDavid Howells
2015-04-11make new_sync_{read,write}() staticAl Viro
2015-01-20fs: remove mapping->backing_dev_infoChristoph Hellwig
2015-01-20fs: introduce f_op->mmap_capabilities for nommu mmap supportChristoph Hellwig
2014-08-08fs/ramfs/file-nommu.c: replace count*size kzalloc by kcallocFabian Frederick
2014-06-12->splice_write() via ->write_iter()Al Viro
2014-05-06write_iter variants of {__,}generic_file_aio_write()Al Viro
2014-05-06switch simple generic_file_aio_read() users to ->read_iter()Al Viro
2014-01-23fs/ramfs: move ramfs_aops to inode.cAxel Lin
2014-01-23fs/ramfs/file-nommu.c: make ramfs_nommu_get_unmapped_area() and ramfs_nommu_m...Axel Lin
2014-01-21fs/ramfs: don't use module_init for non-modular core codePaul Gortmaker
2013-09-11initmpfs: move rootfs code from fs/ramfs/ to init/Rob Landley
2013-09-11initmpfs: move bdi setup from init_rootfs to init_ramfsRob Landley
2013-09-11initmpfs: replace MS_NOUSER in initramfsRob Landley
2013-02-26Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/vir...Linus Torvalds
2013-02-22new helper: file_inode(file)Al Viro
2013-01-26userns: Allow the userns root to mount ramfs.Eric W. Biederman
2012-07-14don't pass nameidata to ->create()Al Viro
2012-07-11fs: ramfs: file-nommu: add SetPageUptodate()Bob Liu
2012-03-20tidy up after d_make_root() conversionAl Viro
2012-03-20switch open-coded instances of d_make_root() to new helperAl Viro
2012-01-03pohmelfs: propagate umode_tAl Viro
2012-01-03switch ->mknod() to umode_tAl Viro
2012-01-03switch ->create() to umode_tAl Viro
2012-01-03switch vfs_mkdir() and ->mkdir() to umode_tAl Viro
2011-11-02ramfs: remove module leftoversRichard Weinberger
2011-04-14ramfs: fix memleak on no-mmu archBob Liu
2010-10-29convert get_sb_nodev() usersAl Viro
2010-10-25fs: do not assign default i_ino in new_inodeChristoph Hellwig
2010-08-09check ATTR_SIZE contraints in inode_change_okChristoph Hellwig
2010-08-09rename generic_setattrChristoph Hellwig
2010-05-27fs: convert simple fs to new truncateNick Piggin
2010-05-27rename the generic fsync implementationsChristoph Hellwig
2010-05-21ramfs: replace inode uid,gid,mode initialization with helper functionDmitry Monakhov
2010-05-21devtmpfs: support !CONFIG_TMPFSPeter Korsgaard
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-21 03:38:17 +0000
a id='n351' href='#n351'>351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 
/*
 *  Deadline i/o scheduler.
 *
 *  Copyright (C) 2002 Jens Axboe <axboe@kernel.dk>
 */
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
#include <linux/rbtree.h>

/*
 * See Documentation/block/deadline-iosched.txt
 */
static const int read_expire = HZ / 2;  /* max time before a read is submitted. */
static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
static const int writes_starved = 2;    /* max times reads can starve a write */
static const int fifo_batch = 16;       /* # of sequential requests treated as one
				     by the above parameters. For throughput. */

struct deadline_data {
	/*
	 * run time data
	 */

	/*
	 * requests (deadline_rq s) are present on both sort_list and fifo_list
	 */
	struct rb_root sort_list[2];	
	struct list_head fifo_list[2];

	/*
	 * next in sort order. read, write or both are NULL
	 */
	struct request *next_rq[2];
	unsigned int batching;		/* number of sequential requests made */
	sector_t last_sector;		/* head position */
	unsigned int starved;		/* times reads have starved writes */

	/*
	 * settings that change how the i/o scheduler behaves
	 */
	int fifo_expire[2];
	int fifo_batch;
	int writes_starved;
	int front_merges;
};

static void deadline_move_request(struct deadline_data *, struct request *);

static inline struct rb_root *
deadline_rb_root(struct deadline_data *dd, struct request *rq)
{
	return &dd->sort_list[rq_data_dir(rq)];
}

/*
 * get the request after `rq' in sector-sorted order
 */
static inline struct request *
deadline_latter_request(struct request *rq)
{
	struct rb_node *node = rb_next(&rq->rb_node);

	if (node)
		return rb_entry_rq(node);

	return NULL;
}

static void
deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
{
	struct rb_root *root = deadline_rb_root(dd, rq);

	elv_rb_add(root, rq);
}

static inline void
deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
{
	const int data_dir = rq_data_dir(rq);

	if (dd->next_rq[data_dir] == rq)
		dd->next_rq[data_dir] = deadline_latter_request(rq);

	elv_rb_del(deadline_rb_root(dd, rq), rq);
}

/*
 * add rq to rbtree and fifo
 */
static void
deadline_add_request(struct request_queue *q, struct request *rq)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	const int data_dir = rq_data_dir(rq);

	deadline_add_rq_rb(dd, rq);

	/*
	 * set expire time and add to fifo list
	 */
	rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
	list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}

/*
 * remove rq from rbtree and fifo.
 */
static void deadline_remove_request(struct request_queue *q, struct request *rq)
{
	struct deadline_data *dd = q->elevator->elevator_data;

	rq_fifo_clear(rq);
	deadline_del_rq_rb(dd, rq);
}

static int
deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	struct request *__rq;
	int ret;

	/*
	 * check for front merge
	 */
	if (dd->front_merges) {
		sector_t sector = bio_end_sector(bio);

		__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
		if (__rq) {
			BUG_ON(sector != blk_rq_pos(__rq));

			if (elv_rq_merge_ok(__rq, bio)) {
				ret = ELEVATOR_FRONT_MERGE;
				goto out;
			}
		}
	}

	return ELEVATOR_NO_MERGE;
out:
	*req = __rq;
	return ret;
}

static void deadline_merged_request(struct request_queue *q,
				    struct request *req, int type)
{
	struct deadline_data *dd = q->elevator->elevator_data;

	/*
	 * if the merge was a front merge, we need to reposition request
	 */
	if (type == ELEVATOR_FRONT_MERGE) {
		elv_rb_del(deadline_rb_root(dd, req), req);
		deadline_add_rq_rb(dd, req);
	}
}

static void
deadline_merged_requests(struct request_queue *q, struct request *req,
			 struct request *next)
{
	/*
	 * if next expires before rq, assign its expire time to rq
	 * and move into next position (next will be deleted) in fifo
	 */
	if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
		if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
			list_move(&req->queuelist, &next->queuelist);
			rq_set_fifo_time(req, rq_fifo_time(next));
		}
	}

	/*
	 * kill knowledge of next, this one is a goner
	 */
	deadline_remove_request(q, next);
}

/*
 * move request from sort list to dispatch queue.
 */
static inline void
deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
{
	struct request_queue *q = rq->q;

	deadline_remove_request(q, rq);
	elv_dispatch_add_tail(q, rq);
}

/*
 * move an entry to dispatch queue
 */
static void
deadline_move_request(struct deadline_data *dd, struct request *rq)
{
	const int data_dir = rq_data_dir(rq);

	dd->next_rq[READ] = NULL;
	dd->next_rq[WRITE] = NULL;
	dd->next_rq[data_dir] = deadline_latter_request(rq);

	dd->last_sector = rq_end_sector(rq);

	/*
	 * take it off the sort and fifo list, move
	 * to dispatch queue
	 */
	deadline_move_to_dispatch(dd, rq);
}

/*
 * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
 * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
 */
static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
{
	struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);

	/*
	 * rq is expired!
	 */
	if (time_after_eq(jiffies, rq_fifo_time(rq)))
		return 1;

	return 0;
}

/*
 * deadline_dispatch_requests selects the best request according to
 * read/write expire, fifo_batch, etc
 */
static int deadline_dispatch_requests(struct request_queue *q, int force)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	const int reads = !list_empty(&dd->fifo_list[READ]);
	const int writes = !list_empty(&dd->fifo_list[WRITE]);
	struct request *rq;
	int data_dir;

	/*
	 * batches are currently reads XOR writes
	 */
	if (dd->next_rq[WRITE])
		rq = dd->next_rq[WRITE];
	else
		rq = dd->next_rq[READ];

	if (rq && dd->batching < dd->fifo_batch)
		/* we have a next request are still entitled to batch */
		goto dispatch_request;

	/*
	 * at this point we are not running a batch. select the appropriate
	 * data direction (read / write)
	 */

	if (reads) {
		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));

		if (writes && (dd->starved++ >= dd->writes_starved))
			goto dispatch_writes;

		data_dir = READ;

		goto dispatch_find_request;
	}

	/*
	 * there are either no reads or writes have been starved
	 */

	if (writes) {
dispatch_writes:
		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));

		dd->starved = 0;

		data_dir = WRITE